Skip to main content

graphrt_rag/
sqlite.rs

1//! Persistent vector store in a single SQLite file.
2//!
3//! [`SqliteStore`] is the durable counterpart of the JSON-backed
4//! [`MemoryStore`]: every change is one SQLite transaction touching only the
5//! affected rows, instead of rewriting the whole file, and several processes
6//! can share one database (SQLite locks it; WAL mode lets readers run while a
7//! writer commits).
8//!
9//! Search runs on an in-process index mirrored from the database, so results
10//! and scores are identical to [`MemoryStore`] (exact cosine, per-dataset BM25,
11//! the same tokenizer). The index holds every chunk in memory, which keeps
12//! queries fast up to a few hundred thousand chunks. Before each operation the
13//! store checks `PRAGMA data_version`; when another connection has committed
14//! since the last sync, the index is reloaded from the file.
15//!
16//! Vectors are stored as little-endian `f32` blobs and metadata as JSON text.
17//! All calls block on SQLite I/O (like [`MemoryStore`] with a file); bulk loads
18//! should upsert in batches, each batch being one transaction.
19
20use std::path::{Path, PathBuf};
21use std::sync::{Mutex, MutexGuard};
22use std::time::Duration;
23
24use futures::future::BoxFuture;
25use rusqlite::{Connection, OptionalExtension, Transaction, params};
26
27use crate::error::RagError;
28use crate::memory::MemoryStore;
29use crate::types::{DocumentSummary, Hit, KeywordQuery, Metadata, StoredChunk, VectorQuery, VectorStore};
30
31/// Version of the table layout written to the `graphrt_meta` table.
32const SCHEMA_VERSION: i64 = 1;
33/// How long a write waits for another process holding the database lock.
34const BUSY_TIMEOUT: Duration = Duration::from_secs(5);
35
36const SCHEMA: &str = "
37CREATE TABLE IF NOT EXISTS graphrt_meta (key TEXT PRIMARY KEY, value TEXT NOT NULL);
38CREATE TABLE IF NOT EXISTS chunks (
39    dataset_id   TEXT NOT NULL,
40    id           TEXT NOT NULL,
41    document_id  TEXT NOT NULL,
42    title        TEXT NOT NULL,
43    text         TEXT NOT NULL,
44    metadata     TEXT NOT NULL,
45    content_hash TEXT NOT NULL,
46    vector       BLOB NOT NULL,
47    PRIMARY KEY (dataset_id, id)
48) WITHOUT ROWID;
49CREATE INDEX IF NOT EXISTS chunks_by_document ON chunks (dataset_id, document_id);
50";
51
52/// [`VectorStore`] persisted in one SQLite file, with cosine and BM25 search.
53///
54/// ```no_run
55/// use std::sync::Arc;
56/// use graphrt_rag::{HashEmbedder, KnowledgeBase, SqliteStore};
57///
58/// let store = SqliteStore::open("knowledge.db")?;
59/// let kb = KnowledgeBase::new().with_store_dataset("faq", Arc::new(store), Arc::new(HashEmbedder::new(256)), None);
60/// # let _ = kb;
61/// # Ok::<(), graphrt_rag::RagError>(())
62/// ```
63#[derive(Debug)]
64pub struct SqliteStore {
65    path: PathBuf,
66    state: Mutex<State>,
67}
68
69#[derive(Debug)]
70struct State {
71    connection: Connection,
72    index: MemoryStore,
73    /// `PRAGMA data_version` when `index` was last synced with the file.
74    synced_version: i64,
75    /// Set when the index may disagree with the file (e.g. a failed commit).
76    stale: bool,
77}
78
79impl SqliteStore {
80    /// Open (or create) the database at `path` and load its chunks.
81    ///
82    /// @throws `RagError::Io` when the file cannot be opened, `RagError::Decode`
83    /// when it was written by an unsupported schema version or holds corrupt rows.
84    pub fn open(path: impl Into<PathBuf>) -> Result<Self, RagError> {
85        let path = path.into();
86        let connection =
87            Connection::open(&path).map_err(|e| RagError::Io(format!("cannot open {}: {e}", path.display())))?;
88        prepare_connection(&connection, &path)?;
89        let mut state = State { connection, index: MemoryStore::new(), synced_version: 0, stale: true };
90        state.refresh(&path)?;
91        Ok(Self { path, state: Mutex::new(state) })
92    }
93
94    /// The database file.
95    pub fn path(&self) -> &Path {
96        &self.path
97    }
98
99    /// Number of chunks across all datasets, as of the latest commit.
100    pub fn len(&self) -> Result<usize, RagError> {
101        let mut state = self.lock()?;
102        state.refresh(&self.path)?;
103        Ok(state.index.len())
104    }
105
106    /// Whether the store holds no chunks.
107    pub fn is_empty(&self) -> Result<bool, RagError> {
108        Ok(self.len()? == 0)
109    }
110
111    fn lock(&self) -> Result<MutexGuard<'_, State>, RagError> {
112        self.state.lock().map_err(|_| RagError::Store("sqlite store lock poisoned by an earlier panic".into()))
113    }
114
115    /// Run a read against an index that reflects the latest commit.
116    fn read<T>(&self, f: impl FnOnce(&MemoryStore) -> Result<T, RagError>) -> Result<T, RagError> {
117        let mut state = self.lock()?;
118        state.refresh(&self.path)?;
119        f(&state.index)
120    }
121
122    /// Apply `change` in one transaction, hand its value to `mirror` to update the
123    /// index, then commit. `mirror` runs before the commit so its validation
124    /// errors roll the transaction back; a failed commit marks the index for
125    /// reloading from the file.
126    fn write<T, R>(
127        &self,
128        change: impl FnOnce(&Transaction<'_>) -> Result<T, RagError>,
129        mirror: impl FnOnce(&MemoryStore, T) -> Result<R, RagError>,
130    ) -> Result<R, RagError> {
131        let mut guard = self.lock()?;
132        guard.refresh(&self.path)?;
133        let state = &mut *guard;
134        let transaction = state.connection.transaction().map_err(|e| store_error(&self.path, &e))?;
135        let changed = change(&transaction)?;
136        let result = mirror(&state.index, changed)?;
137        if let Err(e) = transaction.commit() {
138            state.stale = true;
139            return Err(store_error(&self.path, &e));
140        }
141        Ok(result)
142    }
143}
144
145impl State {
146    /// Reload the index when another connection committed, or after a failure.
147    fn refresh(&mut self, path: &Path) -> Result<(), RagError> {
148        let version: i64 = self
149            .connection
150            .query_row("PRAGMA data_version", [], |row| row.get(0))
151            .map_err(|e| store_error(path, &e))?;
152        if !self.stale && version == self.synced_version {
153            return Ok(());
154        }
155        let chunks = load_chunks(&self.connection, path)?;
156        self.index.replace_all(chunks)?;
157        self.synced_version = version;
158        self.stale = false;
159        Ok(())
160    }
161}
162
163/// Configure the connection, create the tables and check the schema version.
164fn prepare_connection(connection: &Connection, path: &Path) -> Result<(), RagError> {
165    connection.busy_timeout(BUSY_TIMEOUT).map_err(|e| store_error(path, &e))?;
166    // `journal_mode` answers with the resulting mode; network file systems may refuse WAL.
167    let _mode: String =
168        connection.query_row("PRAGMA journal_mode = WAL", [], |row| row.get(0)).map_err(|e| store_error(path, &e))?;
169    connection.execute_batch(SCHEMA).map_err(|e| store_error(path, &e))?;
170    let stored: Option<String> = connection
171        .query_row("SELECT value FROM graphrt_meta WHERE key = 'schema_version'", [], |row| row.get(0))
172        .optional()
173        .map_err(|e| store_error(path, &e))?;
174    match stored {
175        None => {
176            connection
177                .execute(
178                    "INSERT INTO graphrt_meta (key, value) VALUES ('schema_version', ?1)",
179                    params![SCHEMA_VERSION.to_string()],
180                )
181                .map_err(|e| store_error(path, &e))?;
182            Ok(())
183        }
184        Some(v) if v == SCHEMA_VERSION.to_string() => Ok(()),
185        Some(v) => Err(RagError::Decode(format!(
186            "{}: unsupported store schema version {v} (this build reads {SCHEMA_VERSION})",
187            path.display()
188        ))),
189    }
190}
191
192fn load_chunks(connection: &Connection, path: &Path) -> Result<Vec<StoredChunk>, RagError> {
193    let mut statement = connection
194        .prepare(
195            "SELECT dataset_id, id, document_id, title, text, metadata, content_hash, vector \
196             FROM chunks ORDER BY dataset_id, id",
197        )
198        .map_err(|e| store_error(path, &e))?;
199    let rows = statement
200        .query_map([], |row| {
201            Ok(RawChunk {
202                dataset_id: row.get(0)?,
203                id: row.get(1)?,
204                document_id: row.get(2)?,
205                title: row.get(3)?,
206                text: row.get(4)?,
207                metadata: row.get(5)?,
208                content_hash: row.get(6)?,
209                vector: row.get(7)?,
210            })
211        })
212        .map_err(|e| store_error(path, &e))?;
213    let mut chunks = Vec::new();
214    for row in rows {
215        let raw = row.map_err(|e| store_error(path, &e))?;
216        chunks.push(raw.decode(path)?);
217    }
218    Ok(chunks)
219}
220
221/// A row as read from SQLite, before decoding metadata and vector.
222struct RawChunk {
223    dataset_id: String,
224    id: String,
225    document_id: String,
226    title: String,
227    text: String,
228    metadata: String,
229    content_hash: String,
230    vector: Vec<u8>,
231}
232
233impl RawChunk {
234    fn decode(self, path: &Path) -> Result<StoredChunk, RagError> {
235        let corrupt = |what: String| {
236            RagError::Decode(format!(
237                "{}: chunk `{}` of dataset `{}`: {what}",
238                path.display(),
239                self.id,
240                self.dataset_id
241            ))
242        };
243        let metadata: Metadata =
244            serde_json::from_str(&self.metadata).map_err(|e| corrupt(format!("invalid metadata: {e}")))?;
245        let vector = decode_vector(&self.vector).ok_or_else(|| {
246            corrupt(format!("vector blob of {} bytes is not a whole number of f32 values", self.vector.len()))
247        })?;
248        Ok(StoredChunk {
249            id: self.id,
250            dataset_id: self.dataset_id,
251            document_id: self.document_id,
252            title: self.title,
253            text: self.text,
254            metadata,
255            content_hash: self.content_hash,
256            vector,
257        })
258    }
259}
260
261fn encode_vector(vector: &[f32]) -> Vec<u8> {
262    vector.iter().flat_map(|value| value.to_le_bytes()).collect()
263}
264
265/// `None` when the blob length is not a multiple of 4.
266fn decode_vector(bytes: &[u8]) -> Option<Vec<f32>> {
267    let values = bytes.chunks_exact(4);
268    if !values.remainder().is_empty() {
269        return None;
270    }
271    values.map(|b| <[u8; 4]>::try_from(b).ok().map(f32::from_le_bytes)).collect()
272}
273
274fn store_error(path: &Path, error: &rusqlite::Error) -> RagError {
275    RagError::Store(format!("{}: {error}", path.display()))
276}
277
278fn insert_rows(transaction: &Transaction<'_>, path: &Path, chunks: &[StoredChunk]) -> Result<(), RagError> {
279    let mut statement = transaction
280        .prepare_cached(
281            "INSERT OR REPLACE INTO chunks \
282             (dataset_id, id, document_id, title, text, metadata, content_hash, vector) \
283             VALUES (?1, ?2, ?3, ?4, ?5, ?6, ?7, ?8)",
284        )
285        .map_err(|e| store_error(path, &e))?;
286    for chunk in chunks {
287        let metadata = serde_json::to_string(&chunk.metadata)
288            .map_err(|e| RagError::Store(format!("chunk `{}`: cannot encode metadata: {e}", chunk.id)))?;
289        statement
290            .execute(params![
291                chunk.dataset_id,
292                chunk.id,
293                chunk.document_id,
294                chunk.title,
295                chunk.text,
296                metadata,
297                chunk.content_hash,
298                encode_vector(&chunk.vector),
299            ])
300            .map_err(|e| store_error(path, &e))?;
301    }
302    Ok(())
303}
304
305impl VectorStore for SqliteStore {
306    fn upsert(&self, chunks: Vec<StoredChunk>) -> BoxFuture<'_, Result<(), RagError>> {
307        let result = self.write(
308            |tx| insert_rows(tx, &self.path, &chunks).map(|()| chunks),
309            |index, chunks| index.insert_all(chunks),
310        );
311        Box::pin(futures::future::ready(result))
312    }
313
314    fn delete_document<'a>(
315        &'a self,
316        dataset_id: &'a str,
317        document_id: &'a str,
318    ) -> BoxFuture<'a, Result<usize, RagError>> {
319        let result = self.write(
320            |tx| {
321                tx.execute(
322                    "DELETE FROM chunks WHERE dataset_id = ?1 AND document_id = ?2",
323                    params![dataset_id, document_id],
324                )
325                .map_err(|e| store_error(&self.path, &e))
326            },
327            |index, removed| index.remove_document(dataset_id, document_id).map(|_| removed),
328        );
329        Box::pin(futures::future::ready(result))
330    }
331
332    fn delete_dataset<'a>(&'a self, dataset_id: &'a str) -> BoxFuture<'a, Result<usize, RagError>> {
333        let result = self.write(
334            |tx| {
335                tx.execute("DELETE FROM chunks WHERE dataset_id = ?1", params![dataset_id])
336                    .map_err(|e| store_error(&self.path, &e))
337            },
338            |index, removed| index.remove_dataset(dataset_id).map(|_| removed),
339        );
340        Box::pin(futures::future::ready(result))
341    }
342
343    fn document_chunks<'a>(
344        &'a self,
345        dataset_id: &'a str,
346        document_id: &'a str,
347    ) -> BoxFuture<'a, Result<Vec<StoredChunk>, RagError>> {
348        Box::pin(futures::future::ready(self.read(|index| index.find_document_chunks(dataset_id, document_id))))
349    }
350
351    fn delete_chunks<'a>(&'a self, dataset_id: &'a str, ids: &'a [String]) -> BoxFuture<'a, Result<usize, RagError>> {
352        let result = self.write(
353            |tx| {
354                let mut statement = tx
355                    .prepare_cached("DELETE FROM chunks WHERE dataset_id = ?1 AND id = ?2")
356                    .map_err(|e| store_error(&self.path, &e))?;
357                let mut removed = 0;
358                for id in ids {
359                    removed += statement.execute(params![dataset_id, id]).map_err(|e| store_error(&self.path, &e))?;
360                }
361                Ok(removed)
362            },
363            |index, removed| index.remove_chunks(dataset_id, ids).map(|_| removed),
364        );
365        Box::pin(futures::future::ready(result))
366    }
367
368    fn list_documents<'a>(
369        &'a self,
370        dataset_id: &'a str,
371        limit: usize,
372        after: Option<&'a str>,
373    ) -> BoxFuture<'a, Result<Vec<DocumentSummary>, RagError>> {
374        Box::pin(futures::future::ready(self.read(|index| index.document_summaries(dataset_id, limit, after))))
375    }
376
377    fn search<'a>(&'a self, query: VectorQuery<'a>) -> BoxFuture<'a, Result<Vec<Hit>, RagError>> {
378        Box::pin(futures::future::ready(self.read(|index| index.vector_search(&query))))
379    }
380
381    fn supports_keyword(&self) -> bool {
382        true
383    }
384
385    fn keyword_search<'a>(&'a self, query: KeywordQuery<'a>) -> BoxFuture<'a, Result<Vec<Hit>, RagError>> {
386        Box::pin(futures::future::ready(self.read(|index| index.bm25_search(&query))))
387    }
388
389    fn contains_hash<'a>(
390        &'a self,
391        dataset_id: &'a str,
392        content_hash: &'a str,
393    ) -> BoxFuture<'a, Result<bool, RagError>> {
394        Box::pin(futures::future::ready(self.read(|index| index.has_hash(dataset_id, content_hash))))
395    }
396}
397
398#[cfg(test)]
399mod tests {
400    use super::*;
401
402    fn chunk(id: &str, document_id: &str, text: &str, vector: Vec<f32>) -> StoredChunk {
403        let mut metadata = Metadata::new();
404        metadata.insert("lang".into(), serde_json::Value::String("en".into()));
405        StoredChunk {
406            id: id.into(),
407            dataset_id: "d".into(),
408            document_id: document_id.into(),
409            title: format!("title {id}"),
410            text: text.into(),
411            metadata,
412            content_hash: crate::types::content_hash("d", text),
413            vector,
414        }
415    }
416
417    fn block_on<F: std::future::Future>(f: F) -> F::Output {
418        futures::executor::block_on(f)
419    }
420
421    /// A fresh directory per test, removed when dropped.
422    struct ScratchDir(PathBuf);
423
424    impl ScratchDir {
425        fn new(name: &str) -> Self {
426            let dir = std::env::temp_dir().join(format!("graphrt-rag-sqlite-{name}-{}", std::process::id()));
427            let _ = std::fs::remove_dir_all(&dir);
428            std::fs::create_dir_all(&dir).unwrap();
429            Self(dir)
430        }
431
432        fn db(&self) -> PathBuf {
433            self.0.join("kb.db")
434        }
435    }
436
437    impl Drop for ScratchDir {
438        fn drop(&mut self) {
439            let _ = std::fs::remove_dir_all(&self.0);
440        }
441    }
442
443    fn datasets() -> Vec<String> {
444        vec!["d".to_owned()]
445    }
446
447    #[test]
448    fn chunks_survive_reopening_with_vectors_and_metadata() {
449        let scratch = ScratchDir::new("reopen");
450        let original = chunk("a", "doc", "persist me", vec![0.25, -1.5, 3.0]);
451        {
452            let store = SqliteStore::open(scratch.db()).unwrap();
453            block_on(store.upsert(vec![original.clone()])).unwrap();
454        }
455        let reopened = SqliteStore::open(scratch.db()).unwrap();
456        assert_eq!(reopened.len().unwrap(), 1);
457        assert_eq!(block_on(reopened.document_chunks("d", "doc")).unwrap(), vec![original]);
458    }
459
460    #[test]
461    fn search_results_match_memory_store() {
462        let scratch = ScratchDir::new("parity");
463        let chunks = vec![
464            chunk("1", "a", "the cat sat on the mat", vec![1.0, 0.0, 0.0]),
465            chunk("2", "b", "the dog chased the cat", vec![0.7, 0.7, 0.0]),
466            chunk("3", "c", "quantum entanglement explained", vec![0.0, 0.0, 1.0]),
467        ];
468        let sqlite = SqliteStore::open(scratch.db()).unwrap();
469        let memory = MemoryStore::new();
470        block_on(sqlite.upsert(chunks.clone())).unwrap();
471        block_on(memory.upsert(chunks)).unwrap();
472        let ds = datasets();
473
474        let vector = VectorQuery { datasets: &ds, vector: &[1.0, 0.1, 0.0], top_k: 3, filter: None };
475        assert_eq!(block_on(sqlite.search(vector.clone())).unwrap(), block_on(memory.search(vector)).unwrap());
476        let keyword = KeywordQuery { datasets: &ds, text: "cat quantum", top_k: 3, filter: None };
477        assert_eq!(
478            block_on(sqlite.keyword_search(keyword.clone())).unwrap(),
479            block_on(memory.keyword_search(keyword)).unwrap()
480        );
481    }
482
483    #[test]
484    fn deletes_are_persisted() {
485        let scratch = ScratchDir::new("deletes");
486        let store = SqliteStore::open(scratch.db()).unwrap();
487        block_on(store.upsert(vec![
488            chunk("1", "a", "one", vec![1.0]),
489            chunk("2", "a", "two", vec![1.0]),
490            chunk("3", "b", "three", vec![1.0]),
491            chunk("4", "c", "four", vec![1.0]),
492        ]))
493        .unwrap();
494        assert_eq!(block_on(store.delete_document("d", "a")).unwrap(), 2);
495        assert_eq!(block_on(store.delete_chunks("d", &["3".to_owned(), "missing".to_owned()])).unwrap(), 1);
496        drop(store);
497
498        let reopened = SqliteStore::open(scratch.db()).unwrap();
499        assert_eq!(reopened.len().unwrap(), 1);
500        assert_eq!(block_on(reopened.delete_dataset("d")).unwrap(), 1);
501        assert!(SqliteStore::open(scratch.db()).unwrap().is_empty().unwrap());
502    }
503
504    #[test]
505    fn upsert_replaces_by_id() {
506        let scratch = ScratchDir::new("replace");
507        let store = SqliteStore::open(scratch.db()).unwrap();
508        block_on(store.upsert(vec![chunk("x", "doc", "apple banana", vec![1.0, 0.0])])).unwrap();
509        block_on(store.upsert(vec![chunk("x", "doc", "cherry", vec![0.0, 1.0])])).unwrap();
510        drop(store);
511        let reopened = SqliteStore::open(scratch.db()).unwrap();
512        let stored = block_on(reopened.document_chunks("d", "doc")).unwrap();
513        assert_eq!(stored.len(), 1);
514        assert_eq!(stored[0].text, "cherry");
515    }
516
517    #[test]
518    fn invalid_batch_leaves_file_and_index_unchanged() {
519        let scratch = ScratchDir::new("invalid");
520        let store = SqliteStore::open(scratch.db()).unwrap();
521        block_on(store.upsert(vec![chunk("1", "a", "kept", vec![1.0, 0.0])])).unwrap();
522        let mixed = vec![chunk("2", "b", "ok", vec![1.0, 0.0]), chunk("3", "b", "wrong size", vec![1.0, 0.0, 0.0])];
523        let error = block_on(store.upsert(mixed)).unwrap_err();
524        assert_eq!(error.kind(), "invalid_input");
525        assert_eq!(store.len().unwrap(), 1);
526        drop(store);
527        assert_eq!(SqliteStore::open(scratch.db()).unwrap().len().unwrap(), 1);
528    }
529
530    #[test]
531    fn sees_writes_from_another_connection() {
532        let scratch = ScratchDir::new("shared");
533        let reader = SqliteStore::open(scratch.db()).unwrap();
534        let writer = SqliteStore::open(scratch.db()).unwrap();
535        block_on(writer.upsert(vec![chunk("1", "a", "written elsewhere", vec![1.0])])).unwrap();
536        let ds = datasets();
537        let hits =
538            block_on(reader.keyword_search(KeywordQuery { datasets: &ds, text: "elsewhere", top_k: 1, filter: None }))
539                .unwrap();
540        assert_eq!(hits.len(), 1, "reader reloads after another connection commits");
541        block_on(writer.delete_dataset("d")).unwrap();
542        assert!(reader.is_empty().unwrap());
543    }
544
545    #[test]
546    fn rejects_unknown_schema_version() {
547        let scratch = ScratchDir::new("schema");
548        drop(SqliteStore::open(scratch.db()).unwrap());
549        let connection = Connection::open(scratch.db()).unwrap();
550        connection.execute("UPDATE graphrt_meta SET value = '99' WHERE key = 'schema_version'", []).unwrap();
551        drop(connection);
552        let error = SqliteStore::open(scratch.db()).unwrap_err();
553        assert!(error.to_string().contains("schema version 99"), "{error}");
554    }
555
556    #[test]
557    fn rejects_corrupt_vector_blob() {
558        let scratch = ScratchDir::new("corrupt");
559        drop(SqliteStore::open(scratch.db()).unwrap());
560        let connection = Connection::open(scratch.db()).unwrap();
561        connection
562            .execute("INSERT INTO chunks VALUES ('d', 'bad', 'doc', '', 'x', '{}', 'h', ?1)", params![vec![0u8, 1, 2]])
563            .unwrap();
564        drop(connection);
565        let error = SqliteStore::open(scratch.db()).unwrap_err();
566        assert_eq!(error.kind(), "invalid_response");
567        assert!(error.to_string().contains("chunk `bad`"), "{error}");
568    }
569
570    #[test]
571    fn closing_the_store_checkpoints_the_write_ahead_log() {
572        let scratch = ScratchDir::new("checkpoint");
573        let store = SqliteStore::open(scratch.db()).unwrap();
574        block_on(store.upsert(vec![chunk("1", "a", "flushed on close", vec![1.0])])).unwrap();
575        drop(store);
576        // Bundles copy only the main file, so it must hold every commit once closed.
577        let wal = scratch.0.join("kb.db-wal");
578        assert!(std::fs::metadata(&wal).map_or(true, |m| m.len() == 0), "{} still holds commits", wal.display());
579    }
580
581    #[test]
582    fn vector_encoding_roundtrip() {
583        let vector = vec![0.0, -0.0, 1.5, f32::MIN_POSITIVE, -123.456];
584        assert_eq!(decode_vector(&encode_vector(&vector)).unwrap(), vector);
585        assert!(decode_vector(&[1, 2, 3, 4, 5]).is_none());
586    }
587}