Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666"""Chunk metadata in SQLite; vectors in a memory-mapped float32 matrix.
Brute-force cosine similarity over the whole matrix is well under a millisecond perthousand chunks at 1024 dimensions, so an approximate-nearest-neighbour index wouldadd a dependency and a failure mode for no measurable gain at workspace scale.
A chunk's row number is its position in the matrix, so metadata and vectors mustchange together or a search joins the right vector to the wrong source and returnsa confident wrong answer. Overwriting one matrix file in place cannot give that:whichever of the two is written first, a reader arriving in between sees a mismatchedpair. Each build therefore writes a *new* matrix file and records its generation inthe same transaction as the rows, and readers resolve the generation from inside aread transaction. A reader then always sees a matrix that belongs to the metadata itis holding, and never has to be paused for a writer.
Rewriting that matrix whole at every checkpoint costs the size of the index ratherthan the size of the change, so a build `append()`s instead: new vectors go on theend of the current generation's file and only the new rows are inserted. The matrixgrows before the metadata that names those rows, which leaves vectors nothing pointsat rather than rows pointing past the end. Growing a file in place is confined to onethis store alone holds a name for — see `append()`.
A build writes into a second store — the shadow — and hands the finished result tothe live one with `replace_from()`. The live index therefore keeps serving itsprevious contents for the whole of a multi-hour rebuild instead of shrinking towhatever the run has redone so far."""
from __future__ import annotations
import astimport osimport shutilimport sqlite3from dataclasses import dataclass
import numpy as np
from .paths import DATA_DIR, DB_PATH, VEC_DIR
SCHEMA = """CREATE TABLE IF NOT EXISTS files ( id INTEGER PRIMARY KEY, repo TEXT NOT NULL, rel TEXT NOT NULL, sha TEXT NOT NULL, indexed_at REAL NOT NULL, UNIQUE (repo, rel));CREATE TABLE IF NOT EXISTS chunks ( id INTEGER PRIMARY KEY, file_id INTEGER NOT NULL REFERENCES files(id) ON DELETE CASCADE, row INTEGER NOT NULL, start_line INTEGER NOT NULL, end_line INTEGER NOT NULL, text TEXT NOT NULL);CREATE INDEX IF NOT EXISTS chunks_file ON chunks(file_id);CREATE UNIQUE INDEX IF NOT EXISTS chunks_row ON chunks(row);CREATE TABLE IF NOT EXISTS meta (key TEXT PRIMARY KEY, value TEXT NOT NULL);"""
# Superseded matrices to keep on disk. A search that resolved a generation just# before a checkpoint still has to be able to open it.KEEP_GENERATIONS = 2
def shadow_dir() -> str: """Where a build assembles the index it will hand over when it finishes.
Read from DATA_DIR at call time rather than at import, so tests that point the module at a temporary directory get a shadow beside it. """ return os.path.join(DATA_DIR, "shadow")
def shadow_paths() -> tuple[str, str]: """Database and vector directory of that shadow.""" return os.path.join(shadow_dir(), "index.sqlite3"), os.path.join(shadow_dir(), "vectors")
def discard_shadow() -> None: """Drop a build's working copy. Nothing here is referenced by the live index: a matrix handed over is a second name for the same inode, not a borrowed file.""" shutil.rmtree(shadow_dir(), ignore_errors=True)
def _like_escape(value: str) -> str: """Escape LIKE wildcards so a filter matches literally.""" return value.replace("\\", "\\\\").replace("%", "\\%").replace("_", "\\_")
def _fsync_dir(path: str) -> None: fd = os.open(path, os.O_RDONLY) try: os.fsync(fd) finally: os.close(fd)
# A matrix file is an ordinary .npy, written with a header padded to a fixed size so# that rows can be added to the end and the row count rewritten without the data# moving. numpy's own writer pads to whatever the shape needs, which is a different# length once the row count gains a digit._MAGIC = b"\x93NUMPY\x01\x00"_HEADER_BYTES = 128_ROW_BLOCK = 4096 # rows per write, so writing a matrix never copies all of it
def _write_matrix_header(fh, rows: int, dim: int) -> None: """Write the fixed-size header at the front of the file.""" text = f"{{'descr': '<f4', 'fortran_order': False, 'shape': ({rows}, {dim}), }}" pad = _HEADER_BYTES - len(_MAGIC) - 2 - len(text) - 1 if pad < 0: raise ValueError(f"a {rows}x{dim} shape does not fit the matrix header") fh.seek(0) fh.write(_MAGIC + (_HEADER_BYTES - len(_MAGIC) - 2).to_bytes(2, "little")) fh.write(text.encode("ascii") + b" " * pad + b"\n")
def _write_rows(fh, vectors: np.ndarray) -> None: """Write a float32 matrix at the file's current position, a block at a time.
A whole-matrix `ascontiguousarray` would hold a second copy of a hundred and fifty megabytes while it wrote; a block holds a few. """ for off in range(0, vectors.shape[0], _ROW_BLOCK): block = np.ascontiguousarray(vectors[off : off + _ROW_BLOCK], dtype=np.float32) fh.write(block.tobytes())
def _matrix_layout(path: str) -> tuple[int, int] | None: """Rows and width of a matrix written by `_write_matrix_header`, else None.
Only that fixed-header form can be extended in place: anything else — a matrix from an older version of this file, or another writer — has its data at an offset that a longer row count would run into. """ try: with open(path, "rb") as fh: head = fh.read(_HEADER_BYTES) except OSError: return None if len(head) != _HEADER_BYTES or not head.startswith(_MAGIC): return None prefix = len(_MAGIC) + 2 if int.from_bytes(head[len(_MAGIC) : prefix], "little") != _HEADER_BYTES - prefix: return None try: header = ast.literal_eval(head[prefix:].decode("ascii").strip()) if header["descr"] != "<f4" or header["fortran_order"]: return None rows, dim = header["shape"] return int(rows), int(dim) except (SyntaxError, ValueError, KeyError, TypeError): return None
def _link_or_copy(src: str, dst: str) -> None: """Put `src`'s contents at `dst` without reading a hundred megabytes twice.
A matrix file is never written in place, so two names for one inode are safe and the copy costs nothing. Across filesystems there is no such shortcut. """ try: os.link(src, dst) except OSError: tmp = dst + ".tmp.npy" shutil.copyfile(src, tmp) os.replace(tmp, dst)
@dataclassclass Hit: score: float repo: str rel: str start_line: int end_line: int text: str
class Store: def __init__( self, dim: int = 768, db_path: str | None = None, vec_dir: str | None = None, keep_generations: int = KEEP_GENERATIONS, ): self.db_path = db_path or DB_PATH self.vec_dir = vec_dir or VEC_DIR self.keep_generations = keep_generations os.makedirs(os.path.dirname(self.db_path), exist_ok=True) os.makedirs(self.vec_dir, exist_ok=True) self.dim = dim self.db = sqlite3.connect(self.db_path, timeout=30.0) self.db.row_factory = sqlite3.Row self.db.execute("PRAGMA foreign_keys = ON") self.db.execute("PRAGMA journal_mode = WAL") self.db.executescript(SCHEMA) self.db.commit()
@classmethod def shadow(cls, dim: int = 768) -> "Store": """The store a build writes into while the live one keeps serving.
Only the build reads it, so superseded matrices are dropped immediately instead of being kept around for a search that resolved an older one. """ db_path, vec_dir = shadow_paths() return cls(dim=dim, db_path=db_path, vec_dir=vec_dir, keep_generations=1)
def close(self) -> None: self.db.close()
# -- vector matrix ----------------------------------------------------
def _generation_path(self, generation: int) -> str: return os.path.join(self.vec_dir, f"vectors.{generation:012d}.npy")
def _load_vectors(self, generation: int | None = None) -> np.ndarray | None: """Open the matrix for `generation`, or the one the metadata points at.""" if generation is None: raw = self.get_meta("vector_generation") if raw is None: return None generation = int(raw) path = self._generation_path(generation) if not os.path.exists(path): return None return np.load(path, mmap_mode="r")
def vector_count(self) -> int: vecs = self._load_vectors() return 0 if vecs is None else int(vecs.shape[0])
def _prune_generations(self, current: int) -> None: keep = {self._generation_path(current - i) for i in range(self.keep_generations)} for name in os.listdir(self.vec_dir): if not name.startswith("vectors."): continue path = os.path.join(self.vec_dir, name) if path not in keep: try: os.remove(path) except OSError: pass # A reader may still hold it; the next prune will get it.
# -- writes -----------------------------------------------------------
def _width(self, vectors: np.ndarray) -> int: """The matrix width these vectors imply. An empty set carries none.""" return int(vectors.shape[1]) if vectors.ndim == 2 else self.dim
def rebuild(self, records: list[tuple], vectors: np.ndarray) -> None: """Replace the whole index, atomically from a reader's point of view.
`records` is one tuple per vector row, aligned with `vectors`: (repo, rel, sha, start_line, end_line, text, indexed_at). """ if vectors.shape[0] != len(records): raise ValueError(f"{vectors.shape[0]} vectors for {len(records)} records")
generation = int(self.get_meta("vector_generation") or 0) + 1
# The matrix lands on disk and is durable before anything points at it, so a # crash here leaves an orphan file rather than a dangling reference. path = self._generation_path(generation) tmp = path + ".tmp.npy" with open(tmp, "wb") as fh: _write_matrix_header(fh, vectors.shape[0], self._width(vectors)) _write_rows(fh, vectors) fh.flush() os.fsync(fh.fileno()) os.replace(tmp, path) _fsync_dir(self.vec_dir)
try: with self.db: # one transaction: rows and the generation they belong to self._replace_rows(records, generation) except Exception: try: os.remove(path) except OSError: pass raise
self._prune_generations(generation)
def _replace_rows(self, records, generation: int) -> int: """Swap in a whole set of rows and the generation they belong to.
Must run inside a transaction: everything a reader joins has to change at once. `records` is any iterable of (repo, rel, sha, start_line, end_line, text, indexed_at) in row order. """ self.db.execute("DELETE FROM chunks") self.db.execute("DELETE FROM files") file_ids: dict[tuple[str, str], int] = {} row = -1 for row, rec in enumerate(records): repo, rel, sha, start, end, text, ts = rec key = (repo, rel) fid = file_ids.get(key) if fid is None: cur = self.db.execute( "INSERT INTO files (repo, rel, sha, indexed_at) VALUES (?, ?, ?, ?)", (repo, rel, sha, ts), ) fid = int(cur.lastrowid) file_ids[key] = fid self.db.execute( "INSERT INTO chunks (file_id, row, start_line, end_line, text) " "VALUES (?, ?, ?, ?, ?)", (fid, row, start, end, text), ) self.db.execute( "INSERT INTO meta (key, value) VALUES ('vector_generation', ?) " "ON CONFLICT(key) DO UPDATE SET value = excluded.value", (str(generation),), ) return row + 1
def append(self, records: list[tuple], vectors: np.ndarray) -> None: """Add rows to the end of the index without rewriting what is already there.
This is what a checkpoint costs when it only has to publish its own work: the matrix grows by the vectors handed in and the metadata by the same number of rows, rather than both being written out whole every few minutes.
The matrix is extended before the rows that name those vectors land, so a reader arriving in between sees the previous rows against a longer matrix — vectors nothing points at, which is harmless, rather than rows pointing past the end, which is not. A crash between the two leaves the same state.
Extending happens in place only when this store holds the only name for the file. A matrix handed to another store by `replace_from()` is a second name for one inode, and growing it would reach inside an index that is being searched, so that case writes a new generation instead — the same cost as `rebuild()`, and the rows still only grow by what was added. """ if vectors.shape[0] != len(records): raise ValueError(f"{vectors.shape[0]} vectors for {len(records)} records") if not records: return
generation = int(self.get_meta("vector_generation") or 0) row = self.db.execute("SELECT MAX(row) AS r FROM chunks").fetchone()["r"] first_row = 0 if row is None else int(row) + 1 dim = self._width(vectors)
path = self._generation_path(generation) if generation else None layout = _matrix_layout(path) if path else None extend = ( layout is not None and layout[1] == dim # Room for every row already published; a shorter matrix than that is a # previous crash, and appending after the gap would bake it in. and layout[0] >= first_row and os.stat(path).st_nlink == 1 )
published = generation if extend else generation + 1 if extend: with open(path, "r+b") as fh: fh.seek(_HEADER_BYTES + first_row * dim * 4) _write_rows(fh, vectors) fh.flush() os.fsync(fh.fileno()) # The row count grows only once the rows behind it are durable. _write_matrix_header(fh, first_row + len(records), dim) fh.flush() os.fsync(fh.fileno()) else: previous = self._load_vectors(generation) if generation else None if first_row and (previous is None or previous.shape[0] < first_row): raise ValueError( f"{first_row} rows stored but the matrix holds " f"{0 if previous is None else previous.shape[0]}" ) path = self._generation_path(published) tmp = path + ".tmp.npy" with open(tmp, "wb") as fh: _write_matrix_header(fh, first_row + len(records), dim) if first_row: _write_rows(fh, previous[:first_row]) _write_rows(fh, vectors) fh.flush() os.fsync(fh.fileno()) os.replace(tmp, path) _fsync_dir(self.vec_dir)
try: with self.db: self._insert_rows(records, first_row) if published != generation: self.db.execute( "INSERT INTO meta (key, value) VALUES ('vector_generation', ?) " "ON CONFLICT(key) DO UPDATE SET value = excluded.value", (str(published),), ) except Exception: if published != generation: try: os.remove(path) except OSError: pass raise
if published != generation: self._prune_generations(published)
def _insert_rows(self, records, first_row: int) -> int: """Add rows after the last one, in row order. Must run in a transaction.
`records` is (repo, rel, sha, start_line, end_line, text, indexed_at) per vector. A file already in the index is a caller's error, not a case to merge: its chunks would then sit in two separate stretches of row numbers, and the unique index on (repo, rel) refuses it. """ file_ids: dict[tuple[str, str], int] = {} for offset, rec in enumerate(records): repo, rel, sha, start, end, text, ts = rec key = (repo, rel) fid = file_ids.get(key) if fid is None: cur = self.db.execute( "INSERT INTO files (repo, rel, sha, indexed_at) VALUES (?, ?, ?, ?)", (repo, rel, sha, ts), ) fid = int(cur.lastrowid) file_ids[key] = fid self.db.execute( "INSERT INTO chunks (file_id, row, start_line, end_line, text) " "VALUES (?, ?, ?, ?, ?)", (fid, first_row + offset, start, end, text), ) return len(records)
def truncate(self, rows: int) -> None: """Drop row `rows` and everything after it.
For a build abandoning a repository whose first files a checkpoint already published. The matrix keeps its length: the vectors above the cut become unreferenced, which is the direction that costs nothing, and the next `append()` writes over them. """ with self.db: self.db.execute("DELETE FROM chunks WHERE row >= ?", (rows,)) self.db.execute( "DELETE FROM files WHERE id NOT IN (SELECT file_id FROM chunks)" )
def replace_from(self, other: "Store") -> None: """Publish `other`'s index as this one's, atomically for a reader.
Used in both directions: a build seeds its shadow from the live index so unchanged files keep their vectors, and hands the finished index back the same way. The matrix is put in place under a new generation before anything points at it, and the rows, the metadata and the generation number then land in a single transaction — so a search running concurrently sees either the whole previous index or the whole new one, never rows from one joined to the matrix of the other.
A source whose matrix is shorter than its rows — a run that died between writing the two — contributes only the rows its matrix covers, rather than propagating a dangling reference. """ raw = other.get_meta("vector_generation") if raw is None: return # the other side has published nothing to take source_matrix = other._generation_path(int(raw)) vectors = other._load_vectors(int(raw)) if vectors is None: return n_vectors = int(vectors.shape[0]) n_rows = other.db.execute("SELECT COUNT(*) AS n FROM chunks").fetchone()["n"] kept = min(n_rows, n_vectors) if n_rows > n_vectors: # Cut at a file boundary, never mid-file: a file kept with only some of # its chunks matches on sha next run and keeps the truncation forever. edge = other.db.execute( "SELECT MIN(row) AS r FROM chunks WHERE file_id IN " "(SELECT file_id FROM chunks WHERE row >= ?)", (n_vectors,), ).fetchone()["r"] if edge is not None: kept = min(kept, int(edge))
generation = int(self.get_meta("vector_generation") or 0) + 1 path = self._generation_path(generation) if kept == n_vectors: _link_or_copy(source_matrix, path) else: # Fewer rows than vectors: save the prefix the rows actually use, so the # pair this store publishes is exactly aligned. tmp = path + ".tmp.npy" with open(tmp, "wb") as fh: _write_matrix_header(fh, kept, int(vectors.shape[1])) _write_rows(fh, vectors[:kept]) fh.flush() os.fsync(fh.fileno()) os.replace(tmp, path) _fsync_dir(self.vec_dir)
try: rows = other.db.execute( "SELECT f.repo, f.rel, f.sha, c.start_line, c.end_line, c.text, " "f.indexed_at FROM chunks c JOIN files f ON f.id = c.file_id " "ORDER BY c.row LIMIT ?", (kept,), ) meta = other.db.execute( "SELECT key, value FROM meta WHERE key <> 'vector_generation'" ).fetchall() with self.db: written = self._replace_rows(rows, generation) if written != kept: raise ValueError(f"{written} rows copied where {kept} were expected") for entry in meta: self.db.execute( "INSERT INTO meta (key, value) VALUES (?, ?) " "ON CONFLICT(key) DO UPDATE SET value = excluded.value", (entry["key"], entry["value"]), ) except Exception: try: os.remove(path) except OSError: pass raise
self._prune_generations(generation)
def set_meta(self, key: str, value: str) -> None: with self.db: self.db.execute( "INSERT INTO meta (key, value) VALUES (?, ?) " "ON CONFLICT(key) DO UPDATE SET value = excluded.value", (key, value), )
def get_meta(self, key: str) -> str | None: row = self.db.execute("SELECT value FROM meta WHERE key = ?", (key,)).fetchone() return row["value"] if row else None
# -- reads ------------------------------------------------------------
def all_chunks(self) -> list[sqlite3.Row]: return self.db.execute( "SELECT c.row, c.start_line, c.end_line, c.text, f.repo, f.rel, f.sha " "FROM chunks c JOIN files f ON f.id = c.file_id ORDER BY c.row" ).fetchall()
def _filtered_rows(self, repo: str | None, path_filter: str | None) -> np.ndarray: """Matrix row numbers admitted by the filters, as a sorted array.""" clauses = [] params: list[str] = [] if repo: # Accept either a bare repository name or its full path. clauses.append("(f.repo = ? OR f.repo LIKE ? ESCAPE '\\')") params.extend([repo, "%/" + _like_escape(repo)]) if path_filter: clauses.append("f.rel LIKE ? ESCAPE '\\'") params.append("%" + _like_escape(path_filter) + "%") sql = ( "SELECT c.row FROM chunks c JOIN files f ON f.id = c.file_id WHERE " + " AND ".join(clauses) ) rows = [r["row"] for r in self.db.execute(sql, params)] return np.asarray(sorted(rows), dtype=np.int64)
def search( self, query_vec: np.ndarray, k: int = 10, repo: str | None = None, path_filter: str | None = None, ) -> list[Hit]: if k <= 0: return []
# One read transaction pins a snapshot, so the generation resolved here and # the rows read below cannot straddle a writer's commit. self.db.execute("BEGIN DEFERRED") try: raw = self.get_meta("vector_generation") if raw is None: return [] vecs = self._load_vectors(int(raw)) if vecs is None or vecs.shape[0] == 0: return [] if vecs.shape[1] != query_vec.shape[0]: # The embedding model changed since this index was built. Saying so # beats the shape error the matmul below would raise, and beats any # attempt to score across two embedding spaces. raise ValueError( f"index holds {vecs.shape[1]}-dimensional vectors but the query " f"is {query_vec.shape[0]}-dimensional; rebuild the index" )
scores = vecs @ query_vec.astype(np.float32)
if repo is None and path_filter is None: pool = min(k, len(scores)) candidates = np.argpartition(-scores, pool - 1)[:pool] else: # Narrow to the rows the filter admits and rank within them. Ranking # first and filtering after would need an arbitrary over-fetch, and # any fixed size starves a filter whose matches all rank below it — a # small repository behind a large one returns nothing at all. candidates = self._filtered_rows(repo, path_filter) candidates = candidates[candidates < len(scores)] if candidates.size == 0: return [] pool = min(k, candidates.size) local = np.argpartition(-scores[candidates], pool - 1)[:pool] candidates = candidates[local]
top = candidates[np.argsort(-scores[candidates])]
placeholders = ",".join("?" * len(top)) rows = self.db.execute( f"SELECT c.row, c.start_line, c.end_line, c.text, f.repo, f.rel " f"FROM chunks c JOIN files f ON f.id = c.file_id " f"WHERE c.row IN ({placeholders})", [int(i) for i in top], ).fetchall() finally: self.db.commit()
by_row = {r["row"]: r for r in rows} hits: list[Hit] = [] for idx in top: row = by_row.get(int(idx)) if row is None: continue hits.append( Hit( score=float(scores[idx]), repo=row["repo"], rel=row["rel"], start_line=row["start_line"], end_line=row["end_line"], text=row["text"], ) ) if len(hits) >= k: break return hits
def stats(self) -> dict: nf = self.db.execute("SELECT COUNT(*) AS n FROM files").fetchone()["n"] nc = self.db.execute("SELECT COUNT(*) AS n FROM chunks").fetchone()["n"] repos = self.db.execute( "SELECT repo, COUNT(*) AS n FROM files GROUP BY repo ORDER BY n DESC" ).fetchall() return { "files": nf, "chunks": nc, "vectors": self.vector_count(), "repos": [(r["repo"], r["n"]) for r in repos], "model": self.get_meta("model"), "built_at": self.get_meta("built_at"), "progress": self.get_meta("progress"), "dim": self.get_meta("dim"), }