1use std::{collections::VecDeque, num::NonZeroUsize};
16
17use async_trait::async_trait;
18use committable::{Commitment, Committable};
19use futures::stream::{self, StreamExt, TryStreamExt};
20use hotshot_types::traits::{block_contents::BlockHeader, node_implementation::NodeType};
21use itertools::Itertools;
22use sqlx::{FromRow, Row};
23use tagged_base64::{Tagged, TaggedBase64};
24
25use super::{
26 super::transaction::{query, Transaction, TransactionMode},
27 Database, Db, DecodeError, BLOCK_COLUMNS,
28};
29use crate::{
30 availability::{BlockQueryData, QueryableHeader, QueryablePayload},
31 data_source::storage::{ExplorerStorage, NodeStorage},
32 explorer::{
33 self,
34 errors::{self, NotFound},
35 query_data::TransactionDetailResponse,
36 traits::ExplorerHeader,
37 BalanceAmount, BlockDetail, BlockIdentifier, BlockRange, BlockSummary, ExplorerHistograms,
38 ExplorerSummary, GenesisOverview, GetBlockDetailError, GetBlockSummariesError,
39 GetBlockSummariesRequest, GetExplorerSummaryError, GetSearchResultsError,
40 GetTransactionDetailError, GetTransactionSummariesError, GetTransactionSummariesRequest,
41 MonetaryValue, SearchResult, TransactionIdentifier, TransactionRange, TransactionSummary,
42 TransactionSummaryFilter,
43 },
44 types::HeightIndexed,
45 Header, Payload, QueryError, QueryResult, Transaction as HotshotTransaction,
46};
47
48impl From<sqlx::Error> for GetExplorerSummaryError {
49 fn from(err: sqlx::Error) -> Self {
50 Self::from(QueryError::from(err))
51 }
52}
53
54impl From<sqlx::Error> for GetTransactionDetailError {
55 fn from(err: sqlx::Error) -> Self {
56 Self::from(QueryError::from(err))
57 }
58}
59
60impl From<sqlx::Error> for GetTransactionSummariesError {
61 fn from(err: sqlx::Error) -> Self {
62 Self::from(QueryError::from(err))
63 }
64}
65
66impl From<sqlx::Error> for GetBlockDetailError {
67 fn from(err: sqlx::Error) -> Self {
68 Self::from(QueryError::from(err))
69 }
70}
71
72impl From<sqlx::Error> for GetBlockSummariesError {
73 fn from(err: sqlx::Error) -> Self {
74 Self::from(QueryError::from(err))
75 }
76}
77
78impl From<sqlx::Error> for GetSearchResultsError {
79 fn from(err: sqlx::Error) -> Self {
80 Self::from(QueryError::from(err))
81 }
82}
83
84impl<'r, Types> FromRow<'r, <Db as Database>::Row> for BlockSummary<Types>
85where
86 Types: NodeType,
87 Header<Types>: BlockHeader<Types> + ExplorerHeader<Types>,
88 Payload<Types>: QueryablePayload<Types>,
89{
90 fn from_row(row: &'r <Db as Database>::Row) -> sqlx::Result<Self> {
91 BlockQueryData::<Types>::from_row(row)?
92 .try_into()
93 .decode_error("malformed block summary")
94 }
95}
96
97impl<'r, Types> FromRow<'r, <Db as Database>::Row> for BlockDetail<Types>
98where
99 Types: NodeType,
100 Header<Types>: BlockHeader<Types> + ExplorerHeader<Types>,
101 Payload<Types>: QueryablePayload<Types>,
102 BalanceAmount<Types>: Into<MonetaryValue>,
103{
104 fn from_row(row: &'r <Db as Database>::Row) -> sqlx::Result<Self> {
105 BlockQueryData::<Types>::from_row(row)?
106 .try_into()
107 .decode_error("malformed block detail")
108 }
109}
110
111lazy_static::lazy_static! {
112 static ref GET_BLOCK_SUMMARIES_QUERY_FOR_LATEST: String = {
113 format!(
114 "SELECT {BLOCK_COLUMNS}
115 FROM header AS h
116 JOIN payload AS p ON h.height = p.height
117 ORDER BY h.height DESC
118 LIMIT $1"
119 )
120 };
121
122 static ref GET_BLOCK_SUMMARIES_QUERY_FOR_HEIGHT: String = {
123 format!(
124 "SELECT {BLOCK_COLUMNS}
125 FROM header AS h
126 JOIN payload AS p ON h.height = p.height
127 WHERE h.height <= $1
128 ORDER BY h.height DESC
129 LIMIT $2"
130 )
131 };
132
133 static ref GET_BLOCK_SUMMARIES_QUERY_FOR_HASH: String = {
139 format!(
140 "SELECT {BLOCK_COLUMNS}
141 FROM header AS h
142 JOIN payload AS p ON h.height = p.height
143 WHERE h.height <= (SELECT h1.height FROM header AS h1 WHERE h1.hash = $1)
144 ORDER BY h.height DESC
145 LIMIT $2",
146 )
147 };
148
149 static ref GET_BLOCK_DETAIL_QUERY_FOR_LATEST: String = {
150 format!(
151 "SELECT {BLOCK_COLUMNS}
152 FROM header AS h
153 JOIN payload AS p ON h.height = p.height
154 ORDER BY h.height DESC
155 LIMIT 1"
156 )
157 };
158
159 static ref GET_BLOCK_DETAIL_QUERY_FOR_HEIGHT: String = {
160 format!(
161 "SELECT {BLOCK_COLUMNS}
162 FROM header AS h
163 JOIN payload AS p ON h.height = p.height
164 WHERE h.height = $1
165 ORDER BY h.height DESC
166 LIMIT 1"
167 )
168 };
169
170 static ref GET_BLOCK_DETAIL_QUERY_FOR_HASH: String = {
171 format!(
172 "SELECT {BLOCK_COLUMNS}
173 FROM header AS h
174 JOIN payload AS p ON h.height = p.height
175 WHERE h.hash = $1
176 ORDER BY h.height DESC
177 LIMIT 1"
178 )
179 };
180
181
182 static ref GET_BLOCKS_CONTAINING_TRANSACTIONS_NO_FILTER_QUERY: String = {
183 format!(
184 "SELECT {BLOCK_COLUMNS}
185 FROM header AS h
186 JOIN payload AS p ON h.height = p.height
187 WHERE h.height IN (
188 SELECT t.block_height
189 FROM transactions AS t
190 WHERE (t.block_height, t.ns_id, t.position) <= ($1, $2, $3)
191 ORDER BY t.block_height DESC, t.ns_id DESC, t.position DESC
192 LIMIT $4
193 )
194 ORDER BY h.height DESC"
195 )
196 };
197
198 static ref GET_BLOCKS_CONTAINING_TRANSACTIONS_IN_NAMESPACE_QUERY: String = {
199 format!(
200 "SELECT {BLOCK_COLUMNS}
201 FROM header AS h
202 JOIN payload AS p ON h.height = p.height
203 WHERE h.height IN (
204 SELECT t.block_height
205 FROM transactions AS t
206 WHERE (t.block_height, t.ns_id, t.position) <= ($1, $2, $3)
207 AND t.ns_id = $5
208 ORDER BY t.block_height DESC, t.ns_id DESC, t.position DESC
209 LIMIT $4
210 )
211 ORDER BY h.height DESC"
212 )
213 };
214
215 static ref GET_TRANSACTION_SUMMARIES_QUERY_FOR_BLOCK: String = {
216 format!(
217 "SELECT {BLOCK_COLUMNS}
218 FROM header AS h
219 JOIN payload AS p ON h.height = p.height
220 WHERE h.height = $1
221 ORDER BY h.height DESC"
222 )
223 };
224
225 static ref GET_TRANSACTION_DETAIL_QUERY_FOR_LATEST: String = {
226 format!(
227 "SELECT {BLOCK_COLUMNS}
228 FROM header AS h
229 JOIN payload AS p ON h.height = p.height
230 WHERE h.height = (
231 SELECT MAX(t1.block_height)
232 FROM transactions AS t1
233 )
234 ORDER BY h.height DESC"
235 )
236 };
237
238 static ref GET_TRANSACTION_DETAIL_QUERY_FOR_HEIGHT_AND_OFFSET: String = {
239 format!(
240 "SELECT {BLOCK_COLUMNS}
241 FROM header AS h
242 JOIN payload AS p ON h.height = p.height
243 WHERE h.height = (
244 SELECT t1.block_height
245 FROM transactions AS t1
246 WHERE t1.block_height = $1
247 ORDER BY t1.block_height, t1.ns_id, t1.position
248 OFFSET $2
249 LIMIT 1
250 )
251 ORDER BY h.height DESC",
252 )
253 };
254
255 static ref GET_TRANSACTION_DETAIL_QUERY_FOR_HASH: String = {
256 format!(
257 "SELECT {BLOCK_COLUMNS}
258 FROM header AS h
259 JOIN payload AS p ON h.height = p.height
260 WHERE h.height = (
261 SELECT t1.block_height
262 FROM transactions AS t1
263 WHERE t1.hash = $1
264 ORDER BY t1.block_height DESC, t1.ns_id DESC, t1.position DESC
265 LIMIT 1
266 )
267 ORDER BY h.height DESC"
268 )
269 };
270}
271
272const EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES: usize = 50;
275
276const EXPLORER_SUMMARY_NUM_BLOCKS: usize = 10;
279
280const EXPLORER_SUMMARY_NUM_TRANSACTIONS: usize = 10;
283
284#[async_trait]
285impl<Mode, Types> ExplorerStorage<Types> for Transaction<Mode>
286where
287 Mode: TransactionMode,
288 Types: NodeType,
289 Payload<Types>: QueryablePayload<Types>,
290 Header<Types>: QueryableHeader<Types> + ExplorerHeader<Types>,
291 crate::Transaction<Types>: explorer::traits::ExplorerTransaction<Types>,
292 BalanceAmount<Types>: Into<explorer::monetary_value::MonetaryValue>,
293{
294 async fn get_block_summaries(
295 &mut self,
296 request: GetBlockSummariesRequest<Types>,
297 ) -> Result<Vec<BlockSummary<Types>>, GetBlockSummariesError> {
298 let request = &request.0;
299
300 let query_stmt = match request.target {
301 BlockIdentifier::Latest => {
302 query(&GET_BLOCK_SUMMARIES_QUERY_FOR_LATEST).bind(request.num_blocks.get() as i64)
303 },
304 BlockIdentifier::Height(height) => query(&GET_BLOCK_SUMMARIES_QUERY_FOR_HEIGHT)
305 .bind(height as i64)
306 .bind(request.num_blocks.get() as i64),
307 BlockIdentifier::Hash(hash) => query(&GET_BLOCK_SUMMARIES_QUERY_FOR_HASH)
308 .bind(hash.to_string())
309 .bind(request.num_blocks.get() as i64),
310 };
311
312 let row_stream = query_stmt.fetch(self.as_mut());
313 let result = row_stream.map(|row| BlockSummary::from_row(&row?));
314
315 Ok(result.try_collect().await?)
316 }
317
318 async fn get_block_detail(
319 &mut self,
320 request: BlockIdentifier<Types>,
321 ) -> Result<BlockDetail<Types>, GetBlockDetailError> {
322 let query_stmt = match request {
323 BlockIdentifier::Latest => query(&GET_BLOCK_DETAIL_QUERY_FOR_LATEST),
324 BlockIdentifier::Height(height) => {
325 query(&GET_BLOCK_DETAIL_QUERY_FOR_HEIGHT).bind(height as i64)
326 },
327 BlockIdentifier::Hash(hash) => {
328 query(&GET_BLOCK_DETAIL_QUERY_FOR_HASH).bind(hash.to_string())
329 },
330 };
331
332 let query_result = query_stmt.fetch_one(self.as_mut()).await?;
333 let block = BlockDetail::from_row(&query_result)?;
334
335 Ok(block)
336 }
337
338 async fn get_transaction_summaries(
339 &mut self,
340 request: GetTransactionSummariesRequest<Types>,
341 ) -> Result<Vec<TransactionSummary<Types>>, GetTransactionSummariesError> {
342 let range = &request.range;
343 let target = &range.target;
344 let filter = &request.filter;
345
346 let transaction_target_query = match target {
349 TransactionIdentifier::Latest => query(
350 "SELECT block_height AS height, ns_id, position FROM transactions ORDER BY block_height DESC, ns_id DESC, position DESC LIMIT 1",
351 ),
352 TransactionIdentifier::HeightAndOffset(height, _) => query(
353 "SELECT block_height AS height, ns_id, position FROM transactions WHERE block_height = $1 ORDER BY ns_id DESC, position DESC LIMIT 1",
354 )
355 .bind(*height as i64),
356 TransactionIdentifier::Hash(hash) => query(
357 "SELECT block_height AS height, ns_id, position FROM transactions WHERE hash = $1 ORDER BY block_height DESC, ns_id DESC, position DESC LIMIT 1",
358 )
359 .bind(hash.to_string()),
360 };
361 let Some(transaction_target) = transaction_target_query
362 .fetch_optional(self.as_mut())
363 .await?
364 else {
365 return Ok(vec![]);
368 };
369
370 let block_height = transaction_target.get::<i64, _>("height") as usize;
371 let namespace = transaction_target.get::<i64, _>("ns_id");
372 let position = transaction_target.get::<i64, _>("position");
373 let offset = if let TransactionIdentifier::HeightAndOffset(_, offset) = target {
374 *offset
375 } else {
376 0
377 };
378
379 let query_stmt = match filter {
387 TransactionSummaryFilter::RollUp(ns) => {
388 query(&GET_BLOCKS_CONTAINING_TRANSACTIONS_IN_NAMESPACE_QUERY)
389 .bind(block_height as i64)
390 .bind(namespace)
391 .bind(position)
392 .bind((range.num_transactions.get() + offset) as i64)
393 .bind((*ns).into())
394 },
395 TransactionSummaryFilter::None => {
396 query(&GET_BLOCKS_CONTAINING_TRANSACTIONS_NO_FILTER_QUERY)
397 .bind(block_height as i64)
398 .bind(namespace)
399 .bind(position)
400 .bind((range.num_transactions.get() + offset) as i64)
401 },
402
403 TransactionSummaryFilter::Block(block) => {
404 query(&GET_TRANSACTION_SUMMARIES_QUERY_FOR_BLOCK).bind(*block as i64)
405 },
406 };
407
408 let block_stream = query_stmt
409 .fetch(self.as_mut())
410 .map(|row| BlockQueryData::from_row(&row?));
411
412 let transaction_summary_stream = block_stream.flat_map(|row| match row {
413 Ok(block) => {
414 tracing::info!(height = block.height(), "selected block");
415 stream::iter(
416 block
417 .enumerate()
418 .filter(|(ix, _)| {
419 if let TransactionSummaryFilter::RollUp(ns) = filter {
420 let tx_ns = QueryableHeader::<Types>::namespace_id(
421 block.header(),
422 &ix.ns_index,
423 );
424 tx_ns.as_ref() == Some(ns)
425 } else {
426 true
427 }
428 })
429 .enumerate()
430 .map(|(index, (_, txn))| {
431 TransactionSummary::try_from((&block, index, txn)).map_err(|err| {
432 QueryError::Error {
433 message: err.to_string(),
434 }
435 })
436 })
437 .collect::<Vec<QueryResult<TransactionSummary<Types>>>>()
438 .into_iter()
439 .rev()
440 .collect::<Vec<QueryResult<TransactionSummary<Types>>>>(),
441 )
442 },
443 Err(err) => stream::iter(vec![Err(err.into())]),
444 });
445
446 let transaction_summary_vec = transaction_summary_stream
447 .try_collect::<Vec<TransactionSummary<Types>>>()
448 .await?;
449
450 Ok(transaction_summary_vec
451 .into_iter()
452 .skip(offset)
453 .skip_while(|txn| {
454 if let TransactionIdentifier::Hash(hash) = target {
455 txn.hash != *hash
456 } else {
457 false
458 }
459 })
460 .take(range.num_transactions.get())
461 .collect::<Vec<TransactionSummary<Types>>>())
462 }
463
464 async fn get_transaction_detail(
465 &mut self,
466 request: TransactionIdentifier<Types>,
467 ) -> Result<TransactionDetailResponse<Types>, GetTransactionDetailError> {
468 let target = request;
469
470 let query_stmt = match target {
471 TransactionIdentifier::Latest => query(&GET_TRANSACTION_DETAIL_QUERY_FOR_LATEST),
472 TransactionIdentifier::HeightAndOffset(height, offset) => {
473 query(&GET_TRANSACTION_DETAIL_QUERY_FOR_HEIGHT_AND_OFFSET)
474 .bind(height as i64)
475 .bind(offset as i64)
476 },
477 TransactionIdentifier::Hash(hash) => {
478 query(&GET_TRANSACTION_DETAIL_QUERY_FOR_HASH).bind(hash.to_string())
479 },
480 };
481
482 let query_row = query_stmt.fetch_one(self.as_mut()).await?;
483 let block = BlockQueryData::<Types>::from_row(&query_row)?;
484
485 let txns = block.enumerate().map(|(_, txn)| txn).collect::<Vec<_>>();
486
487 let (offset, txn) = match target {
488 TransactionIdentifier::Latest => txns.into_iter().enumerate().next_back().ok_or(
489 GetTransactionDetailError::TransactionNotFound(NotFound {
490 key: "Latest".to_string(),
491 }),
492 ),
493 TransactionIdentifier::HeightAndOffset(height, offset) => {
494 txns.into_iter().enumerate().nth(offset).ok_or(
495 GetTransactionDetailError::TransactionNotFound(NotFound {
496 key: format!("at {height} and {offset}"),
497 }),
498 )
499 },
500 TransactionIdentifier::Hash(hash) => txns
501 .into_iter()
502 .enumerate()
503 .find(|(_, txn)| txn.commit() == hash)
504 .ok_or(GetTransactionDetailError::TransactionNotFound(NotFound {
505 key: format!("hash {hash}"),
506 })),
507 }?;
508
509 Ok(TransactionDetailResponse::try_from((&block, offset, txn))?)
510 }
511
512 async fn get_explorer_summary(
513 &mut self,
514 ) -> Result<ExplorerSummary<Types>, GetExplorerSummaryError> {
515 let histograms = {
516 let histogram_query_result = query(
517 "SELECT
518 h.height AS height,
519 h.timestamp AS timestamp,
520 h.timestamp - lead(timestamp) OVER (ORDER BY h.height DESC) AS time,
521 p.size AS size,
522 p.num_transactions AS transactions
523 FROM header AS h
524 JOIN payload AS p ON
525 p.height = h.height
526 WHERE
527 h.height IN (SELECT height FROM header ORDER BY height DESC LIMIT $1)
528 ORDER BY h.height
529 ",
530 )
531 .bind((EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES + 1) as i64)
532 .fetch(self.as_mut());
533
534 let mut histograms: ExplorerHistograms = histogram_query_result
535 .map(|row_stream| {
536 row_stream.map(|row| {
537 let height: i64 = row.try_get("height")?;
538 let timestamp: i64 = row.try_get("timestamp")?;
539 let time: Option<i64> = row.try_get("time")?;
540 let size: Option<i32> = row.try_get("size")?;
541 let num_transactions: i32 = row.try_get("transactions")?;
542
543 Ok((height, timestamp, time, size, num_transactions))
544 })
545 })
546 .try_fold(
547 ExplorerHistograms {
548 block_time: VecDeque::with_capacity(EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES),
549 block_size: VecDeque::with_capacity(EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES),
550 block_transactions: VecDeque::with_capacity(EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES),
551 block_heights: VecDeque::with_capacity(EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES),
552 },
553 |mut histograms: ExplorerHistograms,
554 row: sqlx::Result<(i64, i64, Option<i64>, Option<i32>, i32)>| async {
555 let (height, _timestamp, time, size, num_transactions) = row?;
556
557 histograms.block_time.push_back(time.map(|i| i as u64));
558 histograms.block_size.push_back(size.map(|i| i as u64));
559 histograms.block_transactions.push_back(num_transactions as u64);
560 histograms.block_heights.push_back(height as u64);
561 Ok(histograms)
562 },
563 )
564 .await?;
565
566 while histograms.block_time.len() > EXPLORER_SUMMARY_HISTOGRAM_NUM_ENTRIES {
567 histograms.block_time.pop_front();
568 histograms.block_size.pop_front();
569 histograms.block_transactions.pop_front();
570 histograms.block_heights.pop_front();
571 }
572
573 histograms
574 };
575
576 let genesis_overview = {
577 let blocks = NodeStorage::<Types>::block_height(self).await? as u64;
578 let transactions =
579 NodeStorage::<Types>::count_transactions_in_range(self, .., None).await? as u64;
580 GenesisOverview {
581 rollups: 0,
582 transactions,
583 blocks,
584 }
585 };
586
587 let latest_block: BlockDetail<Types> =
588 self.get_block_detail(BlockIdentifier::Latest).await?;
589
590 let latest_blocks: Vec<BlockSummary<Types>> = self
591 .get_block_summaries(GetBlockSummariesRequest(BlockRange {
592 target: BlockIdentifier::Latest,
593 num_blocks: NonZeroUsize::new(EXPLORER_SUMMARY_NUM_BLOCKS).unwrap(),
594 }))
595 .await?;
596
597 let latest_transactions: Vec<TransactionSummary<Types>> = self
598 .get_transaction_summaries(GetTransactionSummariesRequest {
599 range: TransactionRange {
600 target: TransactionIdentifier::Latest,
601 num_transactions: NonZeroUsize::new(EXPLORER_SUMMARY_NUM_TRANSACTIONS).unwrap(),
602 },
603 filter: TransactionSummaryFilter::None,
604 })
605 .await?;
606
607 Ok(ExplorerSummary {
608 genesis_overview,
609 latest_block,
610 latest_transactions,
611 latest_blocks,
612 histograms,
613 })
614 }
615
616 async fn get_search_results(
617 &mut self,
618 search_query: TaggedBase64,
619 ) -> Result<SearchResult<Types>, GetSearchResultsError> {
620 let search_tag = search_query.tag();
621 let header_tag = Commitment::<Header<Types>>::tag();
622 let tx_tag = Commitment::<HotshotTransaction<Types>>::tag();
623
624 if search_tag != header_tag && search_tag != tx_tag {
625 return Err(GetSearchResultsError::InvalidQuery(errors::BadQuery {}));
626 }
627
628 let search_query_string = search_query.to_string();
629 if search_tag == header_tag {
630 let block_query = format!(
631 "SELECT {BLOCK_COLUMNS}
632 FROM header AS h
633 JOIN payload AS p ON h.height = p.height
634 WHERE h.hash = $1
635 ORDER BY h.height DESC
636 LIMIT 1"
637 );
638 let row = query(block_query.as_str())
639 .bind(&search_query_string)
640 .fetch_one(self.as_mut())
641 .await?;
642
643 let block = BlockSummary::from_row(&row)?;
644
645 Ok(SearchResult {
646 blocks: vec![block],
647 transactions: Vec::new(),
648 })
649 } else {
650 let transactions_query = format!(
651 "SELECT {BLOCK_COLUMNS}
652 FROM header AS h
653 JOIN payload AS p ON h.height = p.height
654 JOIN transactions AS t ON h.height = t.block_height
655 WHERE t.hash = $1
656 ORDER BY h.height DESC
657 LIMIT 5"
658 );
659 let transactions_query_rows = query(transactions_query.as_str())
660 .bind(&search_query_string)
661 .fetch(self.as_mut());
662 let transactions_query_result: Vec<TransactionSummary<Types>> = transactions_query_rows
663 .map(|row| -> Result<Vec<TransactionSummary<Types>>, QueryError>{
664 let block = BlockQueryData::<Types>::from_row(&row?)?;
665 let transactions = block
666 .enumerate()
667 .enumerate()
668 .filter(|(_, (_, txn))| txn.commit().to_string() == search_query_string)
669 .map(|(offset, (_, txn))| {
670 Ok(TransactionSummary::try_from((
671 &block, offset, txn,
672 ))?)
673 })
674 .try_collect::<TransactionSummary<Types>, Vec<TransactionSummary<Types>>, QueryError>()?;
675 Ok(transactions)
676 })
677 .try_collect::<Vec<Vec<TransactionSummary<Types>>>>()
678 .await?
679 .into_iter()
680 .flatten()
681 .collect();
682
683 Ok(SearchResult {
684 blocks: Vec::new(),
685 transactions: transactions_query_result,
686 })
687 }
688 }
689}