Skip to main content

uqa_sql/semantics/
conflict.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Unique-index inference, target validation, and SQL predicate implication.
8use crate::{
9    ast::{BinaryOp, ColumnDef, TableConstraintSet},
10    binding::snapshot::BindingSnapshot,
11    catalog::index::EnforcedKey,
12    plan::AggregateClassifier,
13    plan::{ConflictPlan, ExpressionPlan, InsertPlan},
14    routines::RoutineResolution,
15    SQLError, SQLParam, ScalarExpr as Expr,
16};
17use std::collections::BTreeSet;
18use uqa_core::{memory::ProductionControl, Value};
19
20mod production;
21pub use production::prepare_inference_predicate_with_control;
22
23pub trait ConflictCatalog {
24    fn try_describe_table(&self, table: &str) -> Result<Option<Vec<ColumnDef>>, String>;
25    /// Lend declaration metadata after observing the same stored sequence dependencies as a description. Consumers inspect names, types and constraints, never rewritten default expressions.
26    fn with_column_metadata_with_control(
27        &self,
28        table: &str,
29        control: &ProductionControl<'_>,
30        read: &mut dyn FnMut(&[ColumnDef]) -> Result<(), SQLError>,
31    ) -> Result<bool, SQLError> {
32        control.check()?;
33        let Some(columns) = self.try_describe_table(table).map_err(SQLError::Internal)? else {
34            return Ok(false);
35        };
36        read(&columns)?;
37        Ok(true)
38    }
39    fn enforced_keys(&self, table: &str) -> Result<Vec<EnforcedKey>, String>;
40    fn try_declared_table_constraints(&self, table: &str) -> Result<TableConstraintSet, String>;
41}
42/// Capture the stored-expression catalog scope only when an inference expression requires binding.
43pub trait InferenceBindingScope {
44    fn binding_scope(&self) -> Result<BindingSnapshot, SQLError>;
45    fn binding_scope_with_control(
46        &self,
47        control: &ProductionControl<'_>,
48    ) -> Result<crate::binding::production::ControlledBindingSnapshot, SQLError> {
49        control.check()?;
50        self.binding_scope()?.copy_with_control(control)
51    }
52}
53#[derive(Clone, Copy)]
54pub struct InferenceContext<'a> {
55    pub catalog: &'a dyn ConflictCatalog,
56    pub aggregates: &'a dyn AggregateClassifier,
57    pub routines: &'a dyn RoutineResolution,
58    pub binding: &'a dyn InferenceBindingScope,
59}
60
61/// Analyze the inference clause in the INSERT target's scope before uniqueness arbitration, including commands that produce no input rows.
62pub fn prepare_inference_predicate<'a>(
63    context: InferenceContext<'_>,
64    statement: &'a InsertPlan,
65    params: &[SQLParam],
66) -> Result<std::borrow::Cow<'a, InsertPlan>, SQLError> {
67    let control = ProductionControl::uncontrolled();
68    let Some(command) =
69        prepare_inference_predicate_with_control(context, statement, params, &control)?
70    else {
71        return Ok(std::borrow::Cow::Borrowed(statement));
72    };
73    let crate::plan::CommandPlan::Insert(insert) = command
74        .into_uncontrolled()
75        .expect("ordinary inference command")
76    else {
77        unreachable!("INSERT inference")
78    };
79    Ok(std::borrow::Cow::Owned(*insert))
80}
81
82fn inference_identity(expression: Expr) -> Expr {
83    let control = ProductionControl::uncontrolled();
84    production::inference_identity_owned(
85        crate::plan::OwnedScalarExpr::uncontrolled(expression),
86        &control,
87    )
88    .expect("ordinary inference identity")
89    .finish(&control)
90    .expect("ordinary inference scalar")
91    .into_uncontrolled()
92    .expect("ordinary inference ownership")
93}
94
95/// Match the inference expressions analyzed by [`prepare_inference_predicate`] against the stored unique keys.
96pub fn conflict_key_indices(
97    catalog: &dyn ConflictCatalog,
98    table: &str,
99    keys: &[EnforcedKey],
100    conflict: &ConflictPlan,
101) -> Result<Vec<usize>, SQLError> {
102    if let Some(name) = &conflict.constraint {
103        return constraint_target_index(catalog, table, keys, name);
104    }
105    if conflict.conflict_columns.is_empty() && conflict.expressions.is_empty() {
106        return Ok((0..keys.len()).collect());
107    }
108    validate_conflict_columns(catalog, table, &conflict.conflict_columns)?;
109    let target = conflict
110        .conflict_columns
111        .iter()
112        .map(String::as_str)
113        .collect::<BTreeSet<_>>();
114    let indexes = keys
115        .iter()
116        .enumerate()
117        .filter_map(|(index, key)| {
118            (key.columns
119                .iter()
120                .map(String::as_str)
121                .collect::<BTreeSet<_>>()
122                == target
123                && {
124                    let expressions = key
125                        .keys
126                        .iter()
127                        .filter_map(|key| match key {
128                            crate::ast::IndexKey::Expression(expr) => Some(inference_identity(
129                                ExpressionPlan::lower((**expr).clone()).scalar,
130                            )),
131                            crate::ast::IndexKey::Column(_) => None,
132                        })
133                        .collect::<Vec<_>>();
134                    expressions
135                        .iter()
136                        .all(|expr| conflict.expressions.contains(expr))
137                        && conflict
138                            .expressions
139                            .iter()
140                            .all(|expr| expressions.contains(expr))
141                }
142                && key.predicate.as_deref().is_none_or(|required| {
143                    conflict.predicate.as_deref().is_some_and(|given| {
144                        implies(
145                            given,
146                            &inference_identity(ExpressionPlan::lower(required.clone()).scalar),
147                        )
148                    })
149                }))
150            .then_some(index)
151        })
152        .collect::<Vec<_>>();
153    if indexes.is_empty() {
154        return Err(SQLError::Routine {
155            sqlstate: "42P10".into(),
156            message:
157                "there is no unique or exclusion constraint matching the ON CONFLICT specification"
158                    .into(),
159        });
160    }
161    Ok(indexes)
162}
163
164/// Prove that every row for which `given` is true also makes `required` true. SQL NULL is never treated as false in a proof that would admit an invalid arbiter.
165fn implies(given: &Expr, required: &Expr) -> bool {
166    if given == required || matches!(required, Expr::Literal(Value::Bool(true))) {
167        return true;
168    }
169    if matches!(given, Expr::Literal(Value::Bool(false) | Value::Null)) {
170        return true;
171    }
172    if let Expr::And(parts) = required {
173        return parts.iter().all(|part| implies(given, part));
174    }
175    if let Expr::Or(parts) = given {
176        return parts.iter().all(|part| implies(part, required));
177    }
178    if let Expr::And(parts) = given {
179        if parts.iter().any(|part| implies(part, required)) {
180            return true;
181        }
182    }
183    if let Expr::Or(parts) = required {
184        return parts.iter().any(|part| implies(given, part));
185    }
186    if let Some((left, given_op, given_value)) = comparison(given) {
187        if let Some((right, required_op, required_value)) = comparison(required) {
188            return left == right
189                && comparison_implies(given_op, given_value, required_op, required_value);
190        }
191        if let Expr::IsNull {
192            expr,
193            negated: true,
194        } = required
195        {
196            return left == expr.as_ref() && !matches!(given_value, Value::Null);
197        }
198    }
199    false
200}
201
202fn comparison(expr: &Expr) -> Option<(&Expr, BinaryOp, &Value)> {
203    let Expr::Binary { op, lhs, rhs } = expr else {
204        return None;
205    };
206    if !matches!(
207        op,
208        BinaryOp::Equal
209            | BinaryOp::NotEqual
210            | BinaryOp::Less
211            | BinaryOp::LessEqual
212            | BinaryOp::Greater
213            | BinaryOp::GreaterEqual
214    ) {
215        return None;
216    }
217    if let Expr::Literal(value) = rhs.as_ref() {
218        return Some((lhs, *op, value));
219    }
220    if let Expr::Literal(value) = lhs.as_ref() {
221        let reversed = match op {
222            BinaryOp::Less => BinaryOp::Greater,
223            BinaryOp::LessEqual => BinaryOp::GreaterEqual,
224            BinaryOp::Greater => BinaryOp::Less,
225            BinaryOp::GreaterEqual => BinaryOp::LessEqual,
226            other => *other,
227        };
228        return Some((rhs, reversed, value));
229    }
230    None
231}
232
233fn comparison_implies(given: BinaryOp, left: &Value, required: BinaryOp, right: &Value) -> bool {
234    use BinaryOp::{Equal, Greater, GreaterEqual, Less, LessEqual, NotEqual};
235    if matches!(left, Value::Null) || matches!(right, Value::Null) {
236        return false;
237    }
238    if std::mem::discriminant(left) != std::mem::discriminant(right) {
239        return false;
240    }
241    let order = left.cmp(right);
242    match (given, required) {
243        (Equal, Equal) | (NotEqual, NotEqual) => order.is_eq(),
244        (Equal, NotEqual) => !order.is_eq(),
245        (Equal | GreaterEqual, Greater) | (GreaterEqual, NotEqual) => order.is_gt(),
246        (Equal | LessEqual, Less) | (LessEqual, NotEqual) => order.is_lt(),
247        (Equal | Greater | GreaterEqual, GreaterEqual) | (Greater, Greater | NotEqual) => {
248            order.is_ge()
249        }
250        (Equal | Less | LessEqual, LessEqual) | (Less, Less | NotEqual) => order.is_le(),
251        _ => false,
252    }
253}
254
255pub fn validate_conflict_target(
256    catalog: &dyn ConflictCatalog,
257    table: &str,
258    conflict: &ConflictPlan,
259) -> Result<(), SQLError> {
260    let keys = catalog
261        .enforced_keys(table)
262        .map_err(|error| SQLError::Internal(format!("conflict target keys: {error}")))?;
263    conflict_key_indices(catalog, table, &keys, conflict).map(|_| ())
264}
265
266fn constraint_target_index(
267    catalog: &dyn ConflictCatalog,
268    table: &str,
269    keys: &[EnforcedKey],
270    name: &str,
271) -> Result<Vec<usize>, SQLError> {
272    if let Some(index) = keys
273        .iter()
274        .position(|key| key.constraint_owned && key.name.as_deref() == Some(name))
275    {
276        return Ok(vec![index]);
277    }
278    let snapshot = catalog
279        .try_declared_table_constraints(table)
280        .map_err(SQLError::Internal)?;
281    let columns = catalog
282        .try_describe_table(table)
283        .map_err(SQLError::Internal)?
284        .ok_or_else(|| SQLError::UnknownTable(table.into()))?;
285    let exists = snapshot
286        .checks
287        .iter()
288        .any(|check| check.name.as_deref() == Some(name))
289        || snapshot
290            .foreign_keys
291            .iter()
292            .any(|key| key.name.as_deref() == Some(name))
293        || columns.iter().any(|column| {
294            column.not_null_name.as_deref() == Some(name)
295                || column.check_name.as_deref() == Some(name)
296                || column
297                    .references
298                    .as_ref()
299                    .is_some_and(|reference| reference.name.as_deref() == Some(name))
300        });
301    if exists {
302        return Err(SQLError::Routine {
303            sqlstate: "42809".into(),
304            message: "constraint in ON CONFLICT clause has no associated index".into(),
305        });
306    }
307    Err(SQLError::Routine {
308        sqlstate: "42704".into(),
309        message: format!("constraint \"{name}\" for table \"{table}\" does not exist"),
310    })
311}
312
313fn validate_conflict_columns(
314    catalog: &dyn ConflictCatalog,
315    table: &str,
316    names: &[String],
317) -> Result<(), SQLError> {
318    let columns = catalog
319        .try_describe_table(table)
320        .map_err(SQLError::Internal)?
321        .ok_or_else(|| SQLError::UnknownTable(table.into()))?;
322    for name in names {
323        if !columns.iter().any(|column| column.name == *name)
324            && !matches!(
325                name.as_str(),
326                "ctid" | "tableoid" | "xmin" | "xmax" | "cmin" | "cmax"
327            )
328        {
329            return Err(SQLError::UnknownColumn(name.clone()));
330        }
331    }
332    Ok(())
333}
334
335#[cfg(test)]
336mod inference;
337
338#[cfg(test)]
339mod production_tests;
340
341#[cfg(test)]
342mod tests {
343    use super::*;
344
345    #[test]
346    fn inference_implication_ignores_cast_origin_but_preserves_cast_types() {
347        let predicate = |implicit, ty: &str, bound| {
348            inference_identity(Expr::Binary {
349                op: BinaryOp::Greater,
350                lhs: Box::new(Expr::Cast {
351                    implicit,
352                    expr: Box::new(Expr::Column("value".into())),
353                    ty: ty.into(),
354                }),
355                rhs: Box::new(Expr::Literal(Value::Int(bound))),
356            })
357        };
358        for implicit in [false, true] {
359            let required = predicate(implicit, "bigint", 0);
360            let equivalent = predicate(!implicit, "bigint", 0);
361            assert_eq!(required, equivalent);
362            assert!(implies(&equivalent, &required));
363            assert!(implies(&predicate(!implicit, "bigint", 1), &required));
364            assert!(!implies(&predicate(!implicit, "bigint", -1), &required));
365            assert!(!implies(&predicate(!implicit, "integer", 0), &required));
366        }
367    }
368}