use crate::error::{Failure, Result};
use core::ops::ControlFlow;
use mysql_async::Column as Declared;
use serde_json::{json, Value};
use sqlparser::ast::{
Expr, Query, Select, SelectItem, SetExpr, Statement, TableFactor, Visit, Visitor,
};
use std::collections::BTreeMap;
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Source {
pub table: String,
pub column: String,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Column {
pub name: String,
pub sources: Vec<Source>,
}
pub fn resolve(statements: &[Statement]) -> Result<Vec<Column>> {
let [Statement::Query(query)] = statements else {
return Err(Failure::validation(
"lineage.not_a_single_query",
"origins can only be resolved for a single statement that returns rows",
)
.with_hint("send one statement that returns rows"));
};
let select = only_select(query)?;
let tables = sources_of(select)?;
select
.projection
.iter()
.map(|item| column_of(item, &tables))
.collect()
}
pub fn resolve_declared(statements: &[Statement], declared: &[Declared]) -> Result<Vec<Column>> {
if declared.is_empty() {
return resolve(statements);
}
let reserve = if declared
.iter()
.any(|column| declared_origin(column).is_none())
{
resolve(statements).unwrap_or_default()
} else {
Vec::new()
};
Ok(crate::exec::read::column_names(declared)
.into_iter()
.enumerate()
.map(|(index, name)| Column {
sources: declared_origin(&declared[index])
.map_or_else(|| reserve_sources(&reserve, index), |source| vec![source]),
name,
})
.collect())
}
#[must_use]
pub fn declared_origin(column: &Declared) -> Option<Source> {
let table = column.org_table_str();
let name = column.org_name_str();
if table.is_empty() || name.is_empty() {
return None;
}
Some(Source {
table: table.into_owned(),
column: name.into_owned(),
})
}
fn reserve_sources(reserve: &[Column], index: usize) -> Vec<Source> {
reserve
.get(index)
.map(|column| column.sources.clone())
.unwrap_or_default()
}
fn only_select(query: &Query) -> Result<&Select> {
match query.body.as_ref() {
SetExpr::Select(select) => Ok(select),
_ => Err(Failure::validation(
"lineage.compound_query",
"the query combines several selections, so a column has no single origin",
)
.with_hint("resolve each selection of the combination on its own")),
}
}
fn sources_of(select: &Select) -> Result<BTreeMap<String, String>> {
let mut tables = BTreeMap::new();
for reference in &select.from {
add_table(&reference.relation, &mut tables)?;
for join in &reference.joins {
add_table(&join.relation, &mut tables)?;
}
}
if tables.is_empty() {
return Ok(tables);
}
Ok(tables)
}
fn add_table(relation: &TableFactor, tables: &mut BTreeMap<String, String>) -> Result<()> {
let TableFactor::Table { name, alias, .. } = relation else {
return Err(Failure::validation(
"lineage.not_a_stored_table",
"the query reads from something that is not a stored table",
)
.with_hint("resolve the origins of the inner query on its own"));
};
let real = name.to_string().replace('`', "");
let referred = alias
.as_ref()
.map_or_else(|| last_part(&real), |alias| alias.name.value.clone());
tables.insert(referred, real);
Ok(())
}
fn last_part(name: &str) -> String {
name.rsplit('.').next().unwrap_or(name).to_owned()
}
fn column_of(item: &SelectItem, tables: &BTreeMap<String, String>) -> Result<Column> {
let (expr, name) = match item {
SelectItem::UnnamedExpr(expr) => (expr, rendered_name(expr)),
SelectItem::ExprWithAlias { expr, alias } => (expr, alias.value.clone()),
SelectItem::Wildcard(_) | SelectItem::QualifiedWildcard(..) => {
return Err(Failure::validation(
"lineage.wildcard",
"the query asks for every column, and which those are is not written in it",
)
.with_hint("name the columns the result should carry"));
}
other @ SelectItem::ExprWithAliases { .. } => {
return Err(Failure::validation(
"lineage.unrecognised_item",
format!("`{other}` has a shape whose origin this tool cannot resolve"),
)
.with_detail("detail", other.to_string())
.with_hint("name the columns the result should carry, one by one"));
}
};
let mut sources = Vec::new();
for reference in references(expr) {
sources.push(resolve_reference(&reference, tables, &name)?);
}
sources.sort();
sources.dedup();
Ok(Column { name, sources })
}
fn rendered_name(expr: &Expr) -> String {
match expr {
Expr::Identifier(ident) => ident.value.clone(),
Expr::CompoundIdentifier(parts) => parts
.last()
.map_or_else(|| expr.to_string(), |ident| ident.value.clone()),
other => other.to_string(),
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
struct Reference {
qualifier: Option<String>,
column: String,
}
fn references(expr: &Expr) -> Vec<Reference> {
let mut collector = Collector::default();
let _ = expr.visit(&mut collector);
collector.found
}
#[derive(Debug, Default)]
struct Collector {
found: Vec<Reference>,
}
impl Visitor for Collector {
type Break = ();
fn pre_visit_expr(&mut self, expr: &Expr) -> ControlFlow<Self::Break> {
match expr {
Expr::Identifier(ident) => self.found.push(Reference {
qualifier: None,
column: ident.value.clone(),
}),
Expr::CompoundIdentifier(parts) => {
if let [qualifier @ .., column] = parts.as_slice() {
self.found.push(Reference {
qualifier: qualifier.last().map(|part| part.value.clone()),
column: column.value.clone(),
});
}
}
_ => {}
}
ControlFlow::Continue(())
}
}
fn resolve_reference(
reference: &Reference,
tables: &BTreeMap<String, String>,
column_name: &str,
) -> Result<Source> {
if let Some(qualifier) = &reference.qualifier {
let table = tables.get(qualifier).ok_or_else(|| {
Failure::validation(
"lineage.unknown_qualifier",
format!("`{qualifier}` is not a table this query reads from"),
)
.with_detail("detail", qualifier.clone())
.with_hint("check the name the column is qualified with")
})?;
return Ok(Source {
table: table.clone(),
column: reference.column.clone(),
});
}
let mut named = tables.values();
match (named.next(), named.next()) {
(Some(only), None) => Ok(Source {
table: only.clone(),
column: reference.column.clone(),
}),
(None, _) => Err(Failure::validation(
"lineage.no_table",
format!("`{}` is not read from any table this query names", reference.column),
)
.with_detail("detail", reference.column.clone())
.with_hint("name the table the column comes from")),
(Some(_), Some(_)) => Err(Failure::validation(
"lineage.ambiguous_column",
format!(
"`{}` in the result column `{column_name}` is not qualified, and the query reads from more than one table",
reference.column
),
)
.with_detail("detail", reference.column.clone())
.with_hint("qualify the column with the table it comes from")),
}
}
#[must_use]
pub fn as_value(columns: &[Column]) -> Value {
json!({
"rows": columns
.iter()
.map(|column| json!({
"column": column.name,
"sources": column
.sources
.iter()
.map(|source| json!({"table": source.table, "column": source.column}))
.collect::<Vec<_>>(),
"computed": column.sources.is_empty(),
}))
.collect::<Vec<_>>(),
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::sql::ParseLimits;
fn parsed(sql: &str) -> Vec<Statement> {
crate::sql::parse(sql, ParseLimits::default()).expect("parses")
}
fn columns(sql: &str) -> Vec<Column> {
resolve(&parsed(sql)).expect("every column must resolve")
}
fn refusal(sql: &str) -> Failure {
resolve(&parsed(sql)).expect_err("the answer must be refused")
}
#[test]
fn a_qualified_column_resolves_to_the_table_it_lives_in() {
let resolved = columns(
"SELECT pedidos.total FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente",
);
assert_eq!(resolved.len(), 1);
assert_eq!(resolved[0].name, "total");
assert_eq!(
resolved[0].sources,
vec![Source {
table: "pedidos".to_owned(),
column: "total".to_owned()
}]
);
}
#[test]
fn an_alias_resolves_to_the_real_table_behind_it() {
let resolved = columns("SELECT p.total FROM pedidos AS p");
assert_eq!(resolved[0].sources[0].table, "pedidos");
}
#[test]
fn an_unqualified_column_over_a_join_refuses_the_whole_answer() {
let failure =
refusal("SELECT total FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente");
assert_eq!(failure.code(), "lineage.ambiguous_column");
assert_eq!(failure.exit_number().code(), 3);
assert!(failure.message().contains("total"));
}
#[test]
fn one_column_that_cannot_be_attributed_refuses_the_other_columns_too() {
let failure = refusal(
"SELECT pedidos.total, cliente FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente",
);
assert_eq!(failure.code(), "lineage.ambiguous_column");
}
#[test]
fn an_unqualified_column_over_one_table_resolves_without_a_guess() {
let resolved = columns("SELECT total FROM pedidos");
assert_eq!(resolved[0].sources[0].table, "pedidos");
assert_eq!(resolved[0].sources[0].column, "total");
}
#[test]
fn a_computed_column_lists_every_physical_column_that_fed_it() {
let resolved = columns("SELECT p.total + p.frete AS bruto FROM pedidos AS p");
assert_eq!(resolved[0].name, "bruto");
assert_eq!(
resolved[0].sources,
vec![
Source {
table: "pedidos".to_owned(),
column: "frete".to_owned()
},
Source {
table: "pedidos".to_owned(),
column: "total".to_owned()
}
]
);
}
#[test]
fn a_column_that_is_a_constant_says_so_rather_than_naming_a_table() {
let resolved = columns("SELECT 1 AS um FROM pedidos");
assert!(resolved[0].sources.is_empty());
assert_eq!(as_value(&resolved)["rows"][0]["computed"], true);
}
#[test]
fn a_wildcard_is_refused_rather_than_expanded_by_guesswork() {
assert_eq!(refusal("SELECT * FROM pedidos").code(), "lineage.wildcard");
assert_eq!(
refusal("SELECT p.* FROM pedidos AS p").code(),
"lineage.wildcard"
);
}
#[test]
fn a_derived_table_is_refused_because_its_columns_are_produced_and_not_stored() {
assert_eq!(
refusal("SELECT s.a FROM (SELECT a FROM t) AS s").code(),
"lineage.not_a_stored_table"
);
}
#[test]
fn a_qualifier_that_names_no_table_of_the_query_is_refused() {
let failure = refusal("SELECT outra.total FROM pedidos");
assert_eq!(failure.code(), "lineage.unknown_qualifier");
assert!(failure.message().contains("outra"));
}
#[test]
fn a_column_with_no_table_at_all_is_refused() {
assert_eq!(refusal("SELECT a").code(), "lineage.no_table");
}
#[test]
fn a_statement_that_does_not_return_rows_has_no_origins_to_resolve() {
for sql in ["DELETE FROM t WHERE a = 1", "CREATE TABLE t (a INT)"] {
assert_eq!(
refusal(sql).code(),
"lineage.not_a_single_query",
"input {sql:?}"
);
}
}
#[test]
fn a_combination_of_selections_is_refused_rather_than_merged() {
assert_eq!(
refusal("SELECT a FROM t UNION SELECT b FROM u").code(),
"lineage.compound_query"
);
}
fn declared(table: &str, name: &str, org_table: &str, org_name: &str) -> Declared {
Declared::new(mysql_async::consts::ColumnType::MYSQL_TYPE_LONG)
.with_table(table.as_bytes())
.with_name(name.as_bytes())
.with_org_table(org_table.as_bytes())
.with_org_name(org_name.as_bytes())
}
#[test]
fn fr_073_the_declared_origin_outranks_the_name_written_in_the_statement() {
let resolved = resolve_declared(
&parsed("SELECT p.total AS bruto FROM pedidos AS p"),
&[declared("p", "bruto", "pedidos", "total")],
)
.expect("the server already resolved it");
assert_eq!(resolved[0].name, "bruto");
assert_eq!(
resolved[0].sources,
vec![Source {
table: "pedidos".to_owned(),
column: "total".to_owned()
}]
);
}
#[test]
fn fr_073_a_column_the_syntax_cannot_attribute_is_answered_from_the_declaration() {
let sql = "SELECT total FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente";
assert_eq!(
refusal(sql).code(),
"lineage.ambiguous_column",
"the syntax alone still refuses"
);
let resolved = resolve_declared(
&parsed(sql),
&[declared("pedidos", "total", "pedidos", "total")],
)
.expect("the declaration leaves nothing ambiguous");
assert_eq!(resolved[0].sources[0].table, "pedidos");
}
#[test]
fn fr_073_a_produced_column_falls_back_to_the_syntax_tree() {
let resolved = resolve_declared(
&parsed("SELECT p.total + p.frete AS bruto FROM pedidos AS p"),
&[declared("", "bruto", "", "")],
)
.expect("the reserve answers the produced column");
assert_eq!(
resolved[0].sources,
vec![
Source {
table: "pedidos".to_owned(),
column: "frete".to_owned()
},
Source {
table: "pedidos".to_owned(),
column: "total".to_owned()
}
]
);
}
#[test]
fn fr_073_a_refused_reserve_does_not_sink_a_declared_answer() {
let resolved = resolve_declared(
&parsed("SELECT *, 1 FROM pedidos"),
&[
declared("pedidos", "total", "pedidos", "total"),
declared("", "1", "", ""),
],
)
.expect("the wildcard refusal stays inside the reserve");
assert_eq!(resolved[0].sources[0].column, "total");
assert!(resolved[1].sources.is_empty(), "a produced column says so");
}
#[test]
fn fr_073_two_homonymous_columns_keep_two_distinct_origins() {
let resolved = resolve_declared(
&parsed("SELECT pedidos.id, clientes.id FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente"),
&[
declared("pedidos", "id", "pedidos", "id"),
declared("clientes", "id", "clientes", "id"),
],
)
.expect("both columns resolve");
assert_eq!(resolved.len(), 2);
assert_eq!(resolved[0].name, "pedidos.id");
assert_eq!(resolved[1].name, "clientes.id");
assert_eq!(resolved[0].sources[0].table, "pedidos");
assert_eq!(resolved[1].sources[0].table, "clientes");
}
#[test]
fn fr_073_without_a_declaration_the_syntax_tree_answers_alone() {
let resolved =
resolve_declared(&parsed("SELECT p.total FROM pedidos AS p"), &[]).expect("resolves");
assert_eq!(resolved, columns("SELECT p.total FROM pedidos AS p"));
assert_eq!(
resolve_declared(
&parsed("SELECT total FROM pedidos JOIN clientes ON clientes.id = pedidos.cliente"),
&[]
)
.expect_err("the refusal is kept")
.code(),
"lineage.ambiguous_column"
);
}
#[test]
fn the_answer_keeps_a_fixed_order_so_two_runs_agree() {
let first = as_value(&columns("SELECT p.total, p.frete FROM pedidos AS p"));
let second = as_value(&columns("SELECT p.total, p.frete FROM pedidos AS p"));
assert_eq!(first, second);
assert_eq!(first["rows"][0]["column"], "total");
assert_eq!(first["rows"][1]["column"], "frete");
}
}