Skip to main content

second_brain_api/
write_gate.rs

1//! Keeps agent writes off the SQLite writer while store maintenance holds
2//! it. A write that arrives then is saved to the write queue and answered
3//! 202; once maintenance ends, writes keep queueing behind the saved ones
4//! until the replayer has sent them all, so none lands out of order.
5
6use std::path::PathBuf;
7use std::sync::atomic::{AtomicUsize, Ordering};
8use std::sync::{Arc, Mutex, MutexGuard};
9use std::time::Duration;
10
11use age::x25519::Recipient;
12use axum::Json;
13use axum::body::{Body, Bytes};
14use axum::extract::{Request, State};
15use axum::http::request::Parts;
16use axum::http::{HeaderValue, Method, StatusCode, header};
17use axum::middleware::Next;
18use axum::response::{IntoResponse, Response};
19use second_brain_core::redact::redact;
20use serde_json::{Value, json};
21use tokio::sync::Notify;
22
23use crate::AppState;
24use crate::clock_gate::ClockGate;
25use crate::write_queue::{self, Entry};
26
27/// Set by the replayer, so a queued write it sends is never queued again.
28pub const REPLAY_HEADER: &str = "x-second-brain-replay";
29pub const QUEUED_REASON: &str = "store maintenance is running; the write is saved when it finishes";
30const RETRY_AFTER_SECS: u64 = 300;
31pub const CLOCK_HELD_REASON: &str =
32    "clock not yet trusted: writes are held until time sync is confirmed; retry later";
33const CLOCK_RETRY_AFTER_SECS: u64 = 30;
34const MAX_QUEUED_BODY: usize = 8 * 1024 * 1024;
35
36#[derive(Debug, Clone, Copy, PartialEq, Eq)]
37enum Mode {
38    Open,
39    Closed,
40    /// Maintenance ended but queued writes are still unsent.
41    Draining,
42}
43
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45enum Class {
46    Read,
47    /// An agent write the replayer can send later.
48    Queueable(&'static str),
49    /// A write whose caller needs the answer now; it retries later.
50    Refused,
51}
52
53pub struct WriteGate {
54    queue_dir: Option<PathBuf>,
55    recipient: Option<Recipient>,
56    mode: Mutex<Mode>,
57    in_flight: AtomicUsize,
58    maintenance: Mutex<()>,
59    reopened: Notify,
60}
61
62impl Default for WriteGate {
63    fn default() -> Self {
64        Self::with_queue(None)
65    }
66}
67
68pub struct WriteSlot<'a>(&'a WriteGate);
69
70impl Drop for WriteSlot<'_> {
71    fn drop(&mut self) {
72        self.0.in_flight.fetch_sub(1, Ordering::SeqCst);
73    }
74}
75
76/// Held for the length of a maintenance run; dropping it lets writes back
77/// in behind whatever was queued meanwhile.
78pub struct Closed<'a> {
79    gate: &'a WriteGate,
80    _serial: MutexGuard<'a, ()>,
81}
82
83impl Drop for Closed<'_> {
84    fn drop(&mut self) {
85        *self.gate.mode() = Mode::Draining;
86        self.gate.reopened.notify_one();
87    }
88}
89
90enum Admission<'a> {
91    Live(WriteSlot<'a>),
92    Queue,
93    Busy,
94}
95
96impl WriteGate {
97    pub fn new(queue_dir: PathBuf) -> Self {
98        Self::with_queue(Some(queue_dir))
99    }
100
101    fn with_queue(queue_dir: Option<PathBuf>) -> Self {
102        Self {
103            queue_dir,
104            recipient: None,
105            mode: Mutex::new(Mode::Open),
106            in_flight: AtomicUsize::new(0),
107            maintenance: Mutex::new(()),
108            reopened: Notify::new(),
109        }
110    }
111
112    pub fn sealing_to(mut self, recipient: Recipient) -> Self {
113        self.recipient = Some(recipient);
114        self
115    }
116
117    pub fn is_closed(&self) -> bool {
118        *self.mode() == Mode::Closed
119    }
120
121    /// Room for an incidental write, such as recall's access count, which
122    /// is skipped rather than queued while maintenance runs.
123    pub fn try_enter(&self) -> Option<WriteSlot<'_>> {
124        match self.admit(Class::Refused, true) {
125            Admission::Live(slot) => Some(slot),
126            Admission::Queue | Admission::Busy => None,
127        }
128    }
129
130    /// Stops new writes and waits for those in flight, so the caller has the
131    /// SQLite writer to itself. Maintenance runs one at a time.
132    pub fn close(&self) -> Closed<'_> {
133        let serial = match self.maintenance.lock() {
134            Ok(g) => g,
135            Err(poisoned) => poisoned.into_inner(),
136        };
137        *self.mode() = Mode::Closed;
138        while self.in_flight.load(Ordering::SeqCst) > 0 {
139            std::thread::sleep(Duration::from_millis(20));
140        }
141        Closed {
142            gate: self,
143            _serial: serial,
144        }
145    }
146
147    /// Keeps other maintenance out without stopping writes, for work that
148    /// only reads the store but must not overlap a rewrite of it.
149    pub fn hold_maintenance(&self) -> MutexGuard<'_, ()> {
150        match self.maintenance.lock() {
151            Ok(g) => g,
152            Err(poisoned) => poisoned.into_inner(),
153        }
154    }
155
156    /// Resolves once maintenance has ended and queued writes wait to be sent.
157    pub async fn reopened(&self) {
158        self.reopened.notified().await;
159    }
160
161    /// Lets writes through again once nothing is left queued; `queue_empty`
162    /// runs under the gate's lock, so no write can be queued after it looked.
163    pub fn open_when_drained(&self, queue_empty: impl FnOnce() -> bool) {
164        let mut mode = self.mode();
165        if *mode == Mode::Draining && queue_empty() {
166            *mode = Mode::Open;
167        }
168    }
169
170    fn admit(&self, class: Class, replay: bool) -> Admission<'_> {
171        let mode = self.mode();
172        let admission = match (*mode, class) {
173            (Mode::Open, _) => Admission::Live(WriteSlot(self)),
174            (Mode::Closed, Class::Queueable(_)) if !replay => Admission::Queue,
175            (Mode::Closed, _) => Admission::Busy,
176            (Mode::Draining, Class::Queueable(_)) if !replay => Admission::Queue,
177            (Mode::Draining, _) => Admission::Live(WriteSlot(self)),
178        };
179        if matches!(admission, Admission::Live(_)) {
180            self.in_flight.fetch_add(1, Ordering::SeqCst);
181        }
182        admission
183    }
184
185    /// Ok(false) when the gate opened since the caller was told to queue.
186    fn enqueue(&self, entry: &Entry) -> anyhow::Result<bool> {
187        let mode = self.mode();
188        if *mode == Mode::Open {
189            return Ok(false);
190        }
191        let Some(dir) = &self.queue_dir else {
192            anyhow::bail!("this daemon has no write queue");
193        };
194        write_queue::push(dir, entry, self.recipient.as_ref())?;
195        Ok(true)
196    }
197
198    fn mode(&self) -> MutexGuard<'_, Mode> {
199        match self.mode.lock() {
200            Ok(g) => g,
201            Err(poisoned) => poisoned.into_inner(),
202        }
203    }
204}
205
206/// GET routes and the POST routes that only read pass untouched, as does
207/// the vacuum route, which closes the gate itself.
208fn classify(method: &Method, path: &str) -> Class {
209    if method == Method::GET || method == Method::HEAD {
210        return Class::Read;
211    }
212    match (method.as_str(), path) {
213        (
214            "POST",
215            "/v1/recall"
216            | "/v1/context"
217            | "/v1/daily/memories"
218            | "/v1/sync/export"
219            | "/v1/sync/snapshot"
220            | "/v1/sync/snapshot/apply"
221            | "/v1/maintenance/vacuum"
222            | "/v1/maintenance/backup",
223        ) => Class::Read,
224        ("POST", "/v1/remember") => Class::Queueable("remember"),
225        ("POST", "/v1/notes") => Class::Queueable("note"),
226        ("POST", "/v1/associate") => Class::Queueable("associate"),
227        ("POST", "/v1/correct") => Class::Queueable("correct"),
228        ("POST", "/v1/ingest") => Class::Queueable("ingest"),
229        ("DELETE", p) if p.starts_with("/v1/memory/") => Class::Queueable("forget"),
230        _ => Class::Refused,
231    }
232}
233
234pub async fn hold_writes(State(state): State<Arc<AppState>>, req: Request, next: Next) -> Response {
235    let class = classify(req.method(), req.uri().path());
236    if class == Class::Read {
237        return next.run(req).await;
238    }
239    let exempt = passes_closed_clock(req.uri().path());
240    if !exempt && !state.clock.is_open() {
241        return clock_held();
242    }
243    let replay = req.headers().contains_key(REPLAY_HEADER);
244    let mut req = req;
245    loop {
246        match state.gate.admit(class, replay) {
247            Admission::Live(slot) => {
248                let response = next.run(req).await;
249                drop(slot);
250                return unless_clock_closed(&state.clock, exempt, response);
251            }
252            Admission::Busy => return busy(),
253            Admission::Queue => {}
254        }
255        let Class::Queueable(tool) = class else {
256            return busy();
257        };
258        let (parts, body) = req.into_parts();
259        let bytes = match axum::body::to_bytes(body, MAX_QUEUED_BODY).await {
260            Ok(b) => b,
261            Err(e) => return error(StatusCode::PAYLOAD_TOO_LARGE, &format!("{e}")),
262        };
263        let entry = match queued_entry(tool, &parts, &bytes) {
264            Ok(entry) => entry,
265            Err(e) => return error(StatusCode::BAD_REQUEST, &e),
266        };
267        let saved = {
268            let (state, entry) = (state.clone(), entry.clone());
269            tokio::task::spawn_blocking(move || state.gate.enqueue(&entry)).await
270        };
271        match saved {
272            Ok(Ok(true)) => return queued(&entry),
273            Ok(Ok(false)) => req = Request::from_parts(parts, Body::from(bytes)),
274            Ok(Err(e)) => {
275                tracing::warn!("cannot queue a {tool} during store maintenance: {e:#}");
276                return busy();
277            }
278            Err(e) => {
279                tracing::warn!("queueing a {tool} during store maintenance failed: {e}");
280                return busy();
281            }
282        }
283    }
284}
285
286/// A remember, note or correct queued without a client id gets one here, so the
287/// caller can name it before it is stored. Text is redacted before it reaches the
288/// queue file, as the handler would before storing it.
289fn queued_entry(tool: &str, parts: &Parts, bytes: &Bytes) -> Result<Entry, String> {
290    let mut body: Option<Value> = if bytes.is_empty() {
291        None
292    } else {
293        Some(serde_json::from_slice(bytes).map_err(|e| format!("invalid JSON body: {e}"))?)
294    };
295    if names_its_write(tool) {
296        let Some(Value::Object(fields)) = body.as_mut() else {
297            return Err(format!("a {tool} needs a JSON object body"));
298        };
299        if !fields.get("id").is_some_and(Value::is_string) {
300            fields.insert(
301                "id".to_string(),
302                Value::String(uuid::Uuid::new_v4().to_string()),
303            );
304        }
305    }
306    if let Some(body) = body.as_mut() {
307        redact_strings(body);
308    }
309    Ok(Entry {
310        tool: tool.to_string(),
311        method: parts.method.to_string(),
312        path: parts.uri.path().to_string(),
313        query: parts.uri.query().map(redact_query),
314        body,
315    })
316}
317
318/// Writes whose reply carries the id of the row they create, so a queued
319/// one is given that id up front.
320fn names_its_write(tool: &str) -> bool {
321    matches!(tool, "remember" | "note" | "correct")
322}
323
324fn redact_strings(value: &mut Value) {
325    match value {
326        Value::String(s) => *s = redact(s).text,
327        Value::Array(items) => items.iter_mut().for_each(redact_strings),
328        Value::Object(fields) => fields.values_mut().for_each(redact_strings),
329        _ => {}
330    }
331}
332
333fn redact_query(query: &str) -> String {
334    let Ok(mut url) = reqwest::Url::parse(&format!("http://queue/?{query}")) else {
335        return redact(query).text;
336    };
337    let pairs: Vec<(String, String)> = url
338        .query_pairs()
339        .map(|(k, v)| (k.into_owned(), redact(&v).text))
340        .collect();
341    url.query_pairs_mut().clear().extend_pairs(pairs);
342    url.query().unwrap_or_default().to_string()
343}
344
345fn queued(entry: &Entry) -> Response {
346    let mut reply = json!({ "queued": true, "reason": QUEUED_REASON });
347    if names_its_write(&entry.tool)
348        && let Some(id) = entry.body.as_ref().and_then(|b| b["id"].as_str())
349    {
350        reply["id"] = Value::String(id.to_string());
351    }
352    (StatusCode::ACCEPTED, Json(reply)).into_response()
353}
354
355fn busy() -> Response {
356    let mut response = error(
357        StatusCode::SERVICE_UNAVAILABLE,
358        "store maintenance is running; retry later",
359    );
360    response
361        .headers_mut()
362        .insert(header::RETRY_AFTER, HeaderValue::from(RETRY_AFTER_SECS));
363    response
364}
365
366/// Sync routes that never mint a seq, or carry the hello that opens the
367/// clock gate.
368fn passes_closed_clock(path: &str) -> bool {
369    matches!(
370        path,
371        "/v1/sync/import"
372            | "/v1/sync/state"
373            | "/v1/sync/hello"
374            | "/v1/sync/accept-hello"
375            | "/v1/sync/ack"
376            | "/v1/sync/peer-in"
377            | "/v1/sync/push-report"
378    )
379}
380
381pub(crate) fn clock_held() -> Response {
382    let mut response = error(StatusCode::SERVICE_UNAVAILABLE, CLOCK_HELD_REASON);
383    response.headers_mut().insert(
384        header::RETRY_AFTER,
385        HeaderValue::from(CLOCK_RETRY_AFTER_SECS),
386    );
387    response
388}
389
390/// A gate that closed while the handler ran (a backward clock step) fails
391/// its store writes, which most handlers answer with a plain 500. Routes
392/// that pass a closed clock map `ClockUntrusted` themselves, so their 500s
393/// are real failures.
394fn unless_clock_closed(clock: &ClockGate, exempt: bool, response: Response) -> Response {
395    if !exempt && response.status() == StatusCode::INTERNAL_SERVER_ERROR && !clock.is_open() {
396        clock_held()
397    } else {
398        response
399    }
400}
401
402fn error(status: StatusCode, message: &str) -> Response {
403    (status, Json(json!({ "error": message }))).into_response()
404}
405
406#[cfg(test)]
407mod tests {
408    use second_brain_core::sqlite_store::clock::ClockUntrusted;
409
410    use super::*;
411
412    #[test]
413    fn holding_maintenance_keeps_writes_open_and_other_maintenance_out() {
414        let gate = Arc::new(WriteGate::default());
415        let held = gate.hold_maintenance();
416        assert!(!gate.is_closed());
417        assert!(gate.try_enter().is_some());
418
419        let (closed_tx, closed) = std::sync::mpsc::channel();
420        let closer = gate.clone();
421        let thread = std::thread::spawn(move || {
422            let _closed = closer.close();
423            closed_tx.send(()).unwrap();
424        });
425        assert!(closed.recv_timeout(Duration::from_millis(200)).is_err());
426        drop(held);
427        closed.recv_timeout(Duration::from_secs(5)).unwrap();
428        thread.join().unwrap();
429    }
430
431    #[test]
432    fn writes_are_told_apart_from_reads() {
433        let post = Method::POST;
434        assert_eq!(classify(&Method::GET, "/v1/redaction"), Class::Read);
435        assert_eq!(classify(&post, "/v1/recall"), Class::Read);
436        assert_eq!(classify(&post, "/v1/maintenance/vacuum"), Class::Read);
437        assert_eq!(classify(&post, "/v1/maintenance/backup"), Class::Read);
438        assert_eq!(
439            classify(&post, "/v1/remember"),
440            Class::Queueable("remember")
441        );
442        assert_eq!(classify(&post, "/v1/notes"), Class::Queueable("note"));
443        assert_eq!(classify(&Method::GET, "/v1/notes"), Class::Read);
444        assert_eq!(
445            classify(&Method::DELETE, "/v1/memory/x"),
446            Class::Queueable("forget")
447        );
448        assert_eq!(classify(&post, "/v1/correct"), Class::Queueable("correct"));
449        assert_eq!(classify(&post, "/v1/sync/import"), Class::Refused);
450        assert_eq!(classify(&post, "/v1/some-new-route"), Class::Refused);
451    }
452
453    #[test]
454    fn a_queued_write_holds_no_secret() {
455        let token = ["gh", "p_"].concat() + "Qq7k3Jd9XwL2pVb8NzR4tYc6MhF1sGa5UeT0";
456        let remember = axum::http::Request::builder()
457            .method("POST")
458            .uri("/v1/remember")
459            .body(())
460            .unwrap()
461            .into_parts()
462            .0;
463        let body = json!({"content": format!("deploy with {token}"), "tags": [token.clone()]});
464        let entry = queued_entry("remember", &remember, &Bytes::from(body.to_string())).unwrap();
465        let forget = axum::http::Request::builder()
466            .method("DELETE")
467            .uri(format!("/v1/memory/x?hard=false&reason=leaked%20{token}"))
468            .body(())
469            .unwrap()
470            .into_parts()
471            .0;
472        let forget = queued_entry("forget", &forget, &Bytes::new()).unwrap();
473        let saved =
474            serde_json::to_string(&entry).unwrap() + &serde_json::to_string(&forget).unwrap();
475        assert!(!saved.contains(&token), "{saved}");
476        assert!(saved.contains("[REDACTED:github_token]"));
477        assert!(entry.body.unwrap()["id"].is_string());
478        assert!(forget.query.unwrap().starts_with("hard=false&reason="));
479    }
480
481    #[test]
482    fn a_queued_note_is_named_before_it_is_stored() {
483        let notes = axum::http::Request::builder()
484            .method("POST")
485            .uri("/v1/notes")
486            .body(())
487            .unwrap()
488            .into_parts()
489            .0;
490        let body = json!({"session_id": "s", "decision": "d"});
491        let entry = queued_entry("note", &notes, &Bytes::from(body.to_string())).unwrap();
492        let id = entry.body.as_ref().unwrap()["id"]
493            .as_str()
494            .unwrap()
495            .to_string();
496        assert_eq!(queued(&entry).status(), StatusCode::ACCEPTED);
497        let again = queued_entry(
498            "note",
499            &notes,
500            &Bytes::from(entry.body.unwrap().to_string()),
501        );
502        assert_eq!(again.unwrap().body.unwrap()["id"], id.as_str());
503    }
504
505    #[test]
506    fn a_queued_correct_gets_a_client_id_it_reports() {
507        let parts = axum::http::Request::builder()
508            .method("POST")
509            .uri("/v1/correct")
510            .body(())
511            .unwrap()
512            .into_parts()
513            .0;
514        let body = json!({"memory_id": "m", "content": "fixed", "evidence": "src/lib.rs:4"});
515        let entry = queued_entry("correct", &parts, &Bytes::from(body.to_string())).unwrap();
516        let id = entry.body.as_ref().unwrap()["id"]
517            .as_str()
518            .unwrap()
519            .to_string();
520        assert!(uuid::Uuid::parse_str(&id).is_ok());
521        let reply = queued(&entry);
522        assert_eq!(reply.status(), StatusCode::ACCEPTED);
523    }
524
525    struct NeverSynced;
526
527    impl crate::clock_gate::TimeSignals for NeverSynced {
528        fn now_micros(&self) -> i64 {
529            0
530        }
531
532        fn ntp_synced(&self) -> bool {
533            false
534        }
535
536        fn rtc_secs(&self) -> Option<i64> {
537            None
538        }
539    }
540
541    fn closed_clock(dir: &std::path::Path) -> Arc<ClockGate> {
542        ClockGate::new(dir, Arc::new(NeverSynced), i64::MAX)
543    }
544
545    fn retry_after(response: &Response) -> Option<&str> {
546        response
547            .headers()
548            .get(header::RETRY_AFTER)
549            .map(|v| v.to_str().unwrap())
550    }
551
552    #[test]
553    fn only_sync_routes_that_mint_nothing_or_carry_a_hello_pass_a_closed_clock() {
554        for path in [
555            "/v1/sync/import",
556            "/v1/sync/state",
557            "/v1/sync/hello",
558            "/v1/sync/accept-hello",
559            "/v1/sync/ack",
560            "/v1/sync/peer-in",
561            "/v1/sync/push-report",
562        ] {
563            assert!(passes_closed_clock(path), "{path}");
564        }
565        for path in [
566            "/v1/remember",
567            "/v1/ingest",
568            "/v1/memory/x",
569            "/v1/sync/compact",
570            "/v1/sync/prune-relations",
571            "/v1/maintenance/repair",
572        ] {
573            assert!(!passes_closed_clock(path), "{path}");
574        }
575    }
576
577    #[test]
578    fn a_held_write_is_told_to_retry_in_thirty_seconds() {
579        let held = clock_held();
580        assert_eq!(held.status(), StatusCode::SERVICE_UNAVAILABLE);
581        assert_eq!(retry_after(&held), Some("30"));
582    }
583
584    #[test]
585    fn a_server_error_while_the_clock_is_closed_is_answered_as_a_held_write() {
586        let dir = tempfile::tempdir().unwrap();
587        let closed = closed_clock(dir.path());
588        assert!(!closed.is_open());
589        let failed = || error(StatusCode::INTERNAL_SERVER_ERROR, "store write failed");
590        let held = unless_clock_closed(&closed, false, failed());
591        assert_eq!(held.status(), StatusCode::SERVICE_UNAVAILABLE);
592        assert_eq!(retry_after(&held), Some("30"));
593
594        let refused = unless_clock_closed(&closed, false, error(StatusCode::BAD_REQUEST, "bad"));
595        assert_eq!(refused.status(), StatusCode::BAD_REQUEST);
596
597        let open = ClockGate::open_for_tests();
598        let failed = unless_clock_closed(&open, false, failed());
599        assert_eq!(failed.status(), StatusCode::INTERNAL_SERVER_ERROR);
600    }
601
602    #[test]
603    fn a_server_error_on_a_sync_route_that_passes_a_closed_clock_stays_a_server_error() {
604        let dir = tempfile::tempdir().unwrap();
605        let closed = closed_clock(dir.path());
606        let failed = error(StatusCode::INTERNAL_SERVER_ERROR, "disk I/O error");
607        let response = unless_clock_closed(&closed, passes_closed_clock("/v1/sync/import"), failed);
608        assert_eq!(response.status(), StatusCode::INTERNAL_SERVER_ERROR);
609        assert_eq!(retry_after(&response), None);
610    }
611
612    #[test]
613    fn a_handler_error_carrying_clock_untrusted_is_a_held_write() {
614        let untrusted = anyhow::Error::new(ClockUntrusted).context("storing a memory");
615        let held = crate::routes::internal_error(untrusted);
616        assert_eq!(held.status(), StatusCode::SERVICE_UNAVAILABLE);
617        assert_eq!(retry_after(&held), Some("30"));
618
619        let other = crate::routes::internal_error(anyhow::anyhow!("database is locked"));
620        assert_eq!(other.status(), StatusCode::INTERNAL_SERVER_ERROR);
621    }
622
623    #[test]
624    fn closing_waits_for_writes_in_flight() {
625        let gate = Arc::new(WriteGate::default());
626        let slot_gate = gate.clone();
627        let (entered, wait) = std::sync::mpsc::channel();
628        let writer = std::thread::spawn(move || {
629            let _slot = slot_gate.try_enter().unwrap();
630            entered.send(()).unwrap();
631            std::thread::sleep(Duration::from_millis(200));
632        });
633        wait.recv().unwrap();
634        let started = std::time::Instant::now();
635        let closed = gate.close();
636        assert!(started.elapsed() >= Duration::from_millis(100));
637        assert!(gate.try_enter().is_none());
638        writer.join().unwrap();
639        drop(closed);
640        assert!(gate.try_enter().is_some());
641    }
642
643    #[test]
644    fn after_maintenance_writes_queue_until_the_queue_drains() {
645        let gate = WriteGate::default();
646        drop(gate.close());
647        assert!(matches!(
648            gate.admit(Class::Queueable("remember"), false),
649            Admission::Queue
650        ));
651        assert!(matches!(
652            gate.admit(Class::Queueable("remember"), true),
653            Admission::Live(_)
654        ));
655        gate.open_when_drained(|| false);
656        assert!(matches!(
657            gate.admit(Class::Queueable("remember"), false),
658            Admission::Queue
659        ));
660        gate.open_when_drained(|| true);
661        assert!(matches!(
662            gate.admit(Class::Queueable("remember"), false),
663            Admission::Live(_)
664        ));
665    }
666}