1use std::cmp::Ordering;
39use std::sync::Arc;
40
41use crate::from_item::ColumnValue;
42use crate::row_scope::RowScope;
43use crate::scope_plan::{is_name, Membership, Planner};
44use crate::scope_row::{item_row_term, RowCondition, RowExpression, RowTerm, RowTest};
45use crate::scope_term::{operand, Affinity, Operand};
46use crate::select_syntax::{order_term, parts, Functions, OrderTerm, Part};
47use crate::sql::unparenthesized;
48use crate::sql_value::SqlValue as Value;
49use rusqlite::Connection;
50use sqlite3_parser::ast::{
51 Distinctness, Expr, OneSelect, ResultColumn, Select, SortOrder, SortedColumn,
52};
53
54pub(crate) struct SortedLimit {
56 runs: Vec<SortRun>,
58 limit: RunLimit,
59}
60
61#[derive(Clone, Debug)]
63pub(crate) struct RunLimit(Operand);
64
65impl RunLimit {
66 pub(crate) fn value(&self, parameters: &[Value]) -> Option<usize> {
69 let Value::Integer(limit) = self.0.value(parameters) else {
70 return None;
71 };
72 usize::try_from(*limit).ok().filter(|limit| *limit > 0)
73 }
74}
75
76pub(crate) struct OrderedLimit<'a> {
81 pub(crate) columns: &'a [ResultColumn<'a>],
82 pub(crate) where_clause: Option<&'a Expr<'a>>,
83 pub(crate) distinct: bool,
84 pub(crate) order_by: &'a [SortedColumn<'a>],
85 pub(crate) limit: RunLimit,
86}
87
88pub(crate) fn ordered_limit<'a>(
91 connection: &Connection,
92 functions: &Functions,
93 select: &'a Select<'a>,
94) -> rusqlite::Result<Option<OrderedLimit<'a>>> {
95 let (Some(limit), Some(order_by)) = (select.limit, select.order_by) else {
96 return Ok(None);
97 };
98 if limit.offset.is_some() || select.body.compounds.is_some() {
99 return Ok(None);
100 }
101 let OneSelect::Select {
102 distinctness,
103 columns,
104 where_clause,
105 group_by: None,
106 having: None,
107 window_clause: None,
108 ..
109 } = &select.body.select
110 else {
111 return Ok(None);
112 };
113 let mut found = Vec::new();
114 for column in columns.iter() {
115 if let ResultColumn::Expr(expr, _) = column {
116 crate::select_syntax::parts(expr, &mut found);
117 }
118 }
119 if found.iter().any(|part| part.many_rows(functions)) {
120 return Ok(None);
121 }
122 let Some(limit) = operand(connection, &limit.expr, Affinity::Blob)? else {
123 return Ok(None);
124 };
125 Ok(Some(OrderedLimit {
126 columns,
127 where_clause: *where_clause,
128 distinct: matches!(distinctness, Some(Distinctness::Distinct)),
129 order_by,
130 limit: RunLimit(limit),
131 }))
132}
133
134struct SortRun {
136 source: usize,
138 terms: Vec<SortTerm>,
139}
140
141struct SortTerm {
143 key: SortKey,
145 descending: bool,
147 position: usize,
149}
150
151enum SortKey {
153 Column(String),
155 Expression(RowExpression),
159}
160
161impl SortKey {
162 fn null(&self, not: bool, parameters: &[Value]) -> RowScope {
165 match self {
166 Self::Column(column) => RowScope::Null { column: column.clone(), not },
167 Self::Expression(RowExpression { term, .. }) => {
168 row(term, parameters, RowTest::Null { not })
169 }
170 }
171 }
172
173 fn compare(&self, value: &Value, ordering: Ordering, parameters: &[Value]) -> RowScope {
176 match self {
177 Self::Column(column) => RowScope::Compare {
178 column: column.clone(),
179 value: value.clone(),
180 ordering,
181 inclusive: false,
182 },
183 Self::Expression(RowExpression { term, affinity }) => row(
184 term,
185 parameters,
186 RowTest::Compare { ordering, value: value.clone(), affinity: *affinity },
187 ),
188 }
189 }
190}
191
192fn row(term: &Arc<RowTerm>, parameters: &[Value], test: RowTest) -> RowScope {
194 RowScope::Row(Arc::new(RowCondition {
195 term: Arc::clone(term),
196 parameters: parameters.to_vec(),
197 test,
198 }))
199}
200
201pub struct LastRow {
203 pub limit: usize,
206 positions: Vec<usize>,
209}
210
211impl LastRow {
212 pub fn values(&self, row: &rusqlite::Row<'_>) -> rusqlite::Result<Vec<Value>> {
214 self.positions.iter().map(|position| Ok(row.get_ref(*position)?.into())).collect()
215 }
216}
217
218impl SortedLimit {
219 pub(crate) fn last_row(&self, parameters: &[Value]) -> Option<LastRow> {
222 Some(LastRow {
223 limit: self.limit.value(parameters)?,
224 positions: self
225 .runs
226 .iter()
227 .flat_map(|run| &run.terms)
228 .map(|term| term.position)
229 .collect(),
230 })
231 }
232
233 pub(crate) fn bound(
241 &self,
242 source: usize,
243 last: &[Value],
244 parameters: &[Value],
245 memberships: &[Membership],
246 looked_up: impl Fn(&Membership, RowScope) -> RowScope,
247 ) -> Option<RowScope> {
248 let mut earlier = Vec::new();
249 let mut values = last;
250 for run in &self.runs {
251 let (own, rest) = values.split_at(run.terms.len());
252 values = rest;
253 if run.source == source {
254 let at_or_before = sorted_before(&run.terms, own, parameters, Some(RowScope::All))
255 .expect("a tied row passes, so some row does");
256 return Some(
257 earlier
258 .into_iter()
259 .rev()
260 .fold(at_or_before, |later, sooner: RowScope| sooner.or(later)),
261 );
262 }
263 let membership = memberships.iter().find(|found| found.partner == run.source)?;
264 if let Some(before) = sorted_before(&run.terms, own, parameters, None) {
265 earlier.push(looked_up(membership, before));
266 }
267 }
268 None
269 }
270}
271
272pub(crate) fn sorted_limit(
275 connection: &Connection,
276 planner: &Planner,
277 select: &Select<'_>,
278 core: usize,
279) -> rusqlite::Result<Option<SortedLimit>> {
280 let Some(OrderedLimit { columns, order_by, limit, .. }) =
281 ordered_limit(connection, planner.functions, select)?
282 else {
283 return Ok(None);
284 };
285 let mut runs: Vec<SortRun> = Vec::new();
286 for term in order_by.iter() {
287 if term.nulls.is_some() {
288 return Ok(None);
289 }
290 let Some((position, item, key)) = sort_term(planner, core, columns, &term.expr) else {
291 return Ok(None);
292 };
293 let from = &planner.items[item];
294 if from.core != core || from.source.table.is_none() || from.left_on.is_some() {
295 return Ok(None);
296 }
297 let term = SortTerm { key, descending: term.order == Some(SortOrder::Desc), position };
298 match runs.last_mut() {
299 Some(run) if run.source == item => run.terms.push(term),
300 _ => runs.push(SortRun { source: item, terms: vec![term] }),
301 }
302 }
303 Ok((!runs.is_empty()).then_some(SortedLimit { runs, limit }))
304}
305
306fn sort_term(
313 planner: &Planner,
314 core: usize,
315 columns: &[ResultColumn<'_>],
316 expr: &Expr<'_>,
317) -> Option<(usize, usize, SortKey)> {
318 let (position, sorted) = match order_term(columns, expr) {
319 OrderTerm::Alias(position, listed) => (position, listed),
320 OrderTerm::Expr(expr) => {
321 let resolved = is_name(expr).then(|| planner.resolve(core, expr)).flatten();
322 let position = columns
325 .iter()
326 .map_while(|column| match column {
327 ResultColumn::Expr(expr, _) => Some(expr),
328 ResultColumn::Star | ResultColumn::TableStar(_) => None,
329 })
330 .position(|listed| match &resolved {
331 Some(resolved) => {
332 is_name(listed) && planner.resolve(core, listed).as_ref() == Some(resolved)
333 }
334 None => unparenthesized(listed) == expr,
335 })?;
336 (position, expr)
337 }
338 OrderTerm::Position(_) | OrderTerm::Unknown => return None,
339 };
340 if is_name(sorted) {
341 let (item, column) = planner.resolve(core, sorted)?;
342 let from = &planner.items[item];
343 let key = match from.columns.value(&column)? {
344 ColumnValue::Compared(_) => SortKey::Column(column),
345 ColumnValue::Generated(generated) => SortKey::Expression(generated.clone()),
346 ColumnValue::Unknown | ColumnValue::Hidden => return None,
347 };
348 return Some((position, item, key));
349 }
350 let mut found = Vec::new();
351 parts(sorted, &mut found);
352 if found.iter().any(|part| matches!(part, Part::Collation)) {
355 return None;
356 }
357 let mut items = found.iter().filter_map(|part| match part {
358 Part::Name(name) => Some(planner.resolve(core, name).map(|(item, _)| item)),
359 _ => None,
360 });
361 let item = items.next()??;
362 if !items.all(|other| other == Some(item)) {
363 return None;
364 }
365 let term = item_row_term(planner, core, item, sorted, &found)?;
366 Some((position, item, SortKey::Expression(RowExpression { term, affinity: Affinity::Blob })))
367}
368
369fn sorted_before(
375 terms: &[SortTerm],
376 last: &[Value],
377 parameters: &[Value],
378 tied: Option<RowScope>,
379) -> Option<RowScope> {
380 let mut scope = tied;
381 for (term, value) in terms.iter().zip(last).rev() {
382 let key = &term.key;
383 let equal = match value {
384 Value::Null => key.null(false, parameters),
385 _ => key.compare(value, Ordering::Equal, parameters),
386 };
387 let before = match (term.descending, value) {
389 (false, Value::Null) => None,
390 (false, _) => {
391 Some(key.null(false, parameters).or(key.compare(value, Ordering::Less, parameters)))
392 }
393 (true, Value::Null) => Some(key.null(true, parameters)),
394 (true, _) => Some(key.compare(value, Ordering::Greater, parameters)),
395 };
396 let tied = scope.map(|scope| equal.and(scope));
397 scope = match (before, tied) {
398 (Some(before), Some(tied)) => Some(before.or(tied)),
399 (before, None) => before,
400 (None, tied) => tied,
401 };
402 }
403 scope
404}