#[cfg(any(feature = "mysql", feature = "postgres"))]
use super::RelationBatchExecutor;
use super::{
PaginatedResult, QueryParams, Record, RelationData, RelationLoader, SortOrder, TableQuery,
WhereCondition, DEFAULT_QUERY_PAGE_SIZE,
};
use crate::definition::CompiledTableView;
use crate::error::BaseError;
use serde_json::Value;
use std::collections::{HashMap, HashSet};
pub const DEFAULT_TREE_MAX_NODES: usize = 10_000;
pub const DEFAULT_TREE_MAX_DEPTH: usize = 1_024;
#[cfg(any(feature = "mysql", feature = "postgres", test))]
fn ensure_tree_node_cap(count: usize, max_nodes: usize) -> Result<(), BaseError> {
if count > max_nodes {
return Err(BaseError::ParamInvalid(
"tree".to_string(),
format!("树节点数 {count} 超过上限 {max_nodes},请先收窄查询范围"),
));
}
Ok(())
}
fn ensure_tree_depth_cap(depth: usize, max_depth: usize) -> Result<(), BaseError> {
if depth > max_depth {
return Err(BaseError::ParamInvalid(
"tree".to_string(),
format!("树嵌套深度 {depth} 超过上限 {max_depth},请先收窄查询范围"),
));
}
Ok(())
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct TableListResult {
pub page: PaginatedResult<Record>,
pub relations: RelationData,
}
#[derive(Debug, Clone, serde::Serialize)]
pub struct TableTreeNode {
#[serde(flatten)]
pub record: Record,
pub children: Vec<TableTreeNode>,
}
#[derive(Debug, Clone)]
pub struct Tables {
query: TableQuery,
relation_loader: RelationLoader,
}
impl Tables {
pub fn new(query: TableQuery) -> Self {
Self {
query,
relation_loader: RelationLoader::default(),
}
}
pub fn view(mut self, view: &CompiledTableView) -> Result<Self, BaseError> {
let fields = view
.fields()
.iter()
.map(|field| {
field
.as_str()
.rsplit_once('.')
.map_or(field.as_str(), |(_, name)| name)
})
.collect::<Vec<_>>();
self.query = self.query.select_fields(&fields)?;
Ok(self)
}
pub fn relations(mut self, loader: RelationLoader) -> Self {
self.relation_loader = loader;
self
}
pub fn where_from(mut self, conditions: &[WhereCondition]) -> Result<Self, BaseError> {
if conditions.is_empty() {
return Ok(self);
}
self.query = self.query.where_and(conditions.to_vec())?;
Ok(self)
}
pub fn search(mut self, keyword: Option<&str>) -> Result<Self, BaseError> {
self.query = self.query.search(keyword)?;
Ok(self)
}
pub fn order(mut self, field: &str, order: SortOrder) -> Result<Self, BaseError> {
self.query = self.query.order_by(field, order)?;
Ok(self)
}
pub fn page(mut self, page: usize, limit: usize) -> Result<Self, BaseError> {
self.query = self.query.page(page, limit)?;
Ok(self)
}
pub fn params(mut self, params: QueryParams) -> Result<Self, BaseError> {
self.query = self.query.apply_params(params)?;
Ok(self)
}
pub fn params_table() -> QueryParams {
QueryParams::new().with_pagination(1, DEFAULT_QUERY_PAGE_SIZE)
}
#[cfg(any(feature = "mysql", feature = "postgres"))]
pub async fn table_list(self) -> Result<PaginatedResult<Record>, BaseError> {
self.query.paginate_records().await
}
#[cfg(any(feature = "mysql", feature = "postgres"))]
pub async fn table_select(self) -> Result<Vec<Record>, BaseError> {
self.query.all().await
}
#[cfg(any(feature = "mysql", feature = "postgres"))]
pub async fn table_tree(self) -> Result<Vec<TableTreeNode>, BaseError> {
let read_limit = DEFAULT_TREE_MAX_NODES
.checked_add(1)
.ok_or_else(|| BaseError::ConfigError("默认树节点上限无法计算截断探针".to_string()))?;
let rows = self.query.prefetch_limit(read_limit)?.all().await?;
ensure_tree_node_cap(rows.len(), DEFAULT_TREE_MAX_NODES)?;
Self::build_tree(rows, "id", "parent_id")
}
#[cfg(any(feature = "mysql", feature = "postgres"))]
pub async fn table_tree_view(
self,
view: &CompiledTableView,
) -> Result<Vec<TableTreeNode>, BaseError> {
let tree = view
.tree()
.ok_or_else(|| BaseError::ConfigError(format!("View {} 未声明树拓扑", view.name())))?;
let max_nodes = tree.max_nodes();
let read_limit = max_nodes.checked_add(1).ok_or_else(|| {
BaseError::ConfigError(format!("View {} 的树节点上限过大", view.name()))
})?;
let rows = self
.view(view)?
.query
.prefetch_limit(read_limit)?
.all()
.await?;
ensure_tree_node_cap(rows.len(), max_nodes)?;
Self::build_tree(rows, tree.id_field_name(), tree.parent_field_name())
}
pub fn build_tree(
rows: Vec<Record>,
id_field: &str,
parent_field: &str,
) -> Result<Vec<TableTreeNode>, BaseError> {
let mut ids = HashMap::with_capacity(rows.len());
for (index, row) in rows.iter().enumerate() {
let id = row.get(id_field).ok_or_else(|| {
BaseError::ParamInvalid(id_field.to_string(), "树节点缺少主键".to_string())
})?;
if id.is_null() {
return Err(BaseError::ParamInvalid(
id_field.to_string(),
"树节点主键不能为 null".to_string(),
));
}
if ids.insert(value_key(id), index).is_some() {
return Err(BaseError::ConfigError(format!(
"树节点主键重复: {id_field}={id}"
)));
}
}
let mut children = vec![Vec::new(); rows.len()];
let mut roots = Vec::new();
for (index, row) in rows.iter().enumerate() {
let parent = row.get(parent_field).unwrap_or(&Value::Null);
if parent.is_null() {
roots.push(index);
} else if let Some(parent_index) = ids.get(&value_key(parent)).copied() {
children[parent_index].push(index);
} else {
roots.push(index);
}
}
let mut rows = rows.into_iter().map(Some).collect::<Vec<_>>();
let mut visiting = HashSet::new();
let mut stack: Vec<TreeBuildFrame> = roots
.iter()
.rev()
.map(|&index| TreeBuildFrame::Enter { index, depth: 1 })
.collect();
let mut pending: Vec<(usize, Record, Vec<TableTreeNode>)> = Vec::new();
let mut nodes = Vec::with_capacity(roots.len());
while let Some(frame) = stack.pop() {
match frame {
TreeBuildFrame::Enter { index, depth } => {
ensure_tree_depth_cap(depth, DEFAULT_TREE_MAX_DEPTH)?;
if !visiting.insert(index) {
return Err(BaseError::ConfigError("树关系包含循环".to_string()));
}
let record = rows[index]
.take()
.ok_or_else(|| BaseError::ConfigError("树节点被重复引用".to_string()))?;
pending.push((index, record, Vec::new()));
stack.push(TreeBuildFrame::Leave { index });
stack.extend(children[index].iter().rev().map(|&child| {
TreeBuildFrame::Enter {
index: child,
depth: depth + 1,
}
}));
}
TreeBuildFrame::Leave { index } => {
visiting.remove(&index);
let (owner, record, child_nodes) =
pending.pop().ok_or_else(work_stack_error)?;
if owner != index {
return Err(work_stack_error());
}
let node = TableTreeNode {
record,
children: child_nodes,
};
match pending.last_mut() {
Some((_, _, siblings)) => siblings.push(node),
None => nodes.push(node),
}
}
}
}
if rows.iter().any(Option::is_some) {
return Err(BaseError::ConfigError("树关系包含循环".to_string()));
}
Ok(nodes)
}
#[cfg(any(feature = "mysql", feature = "postgres"))]
pub async fn table_list_with_relations<E>(
self,
executor: &E,
) -> Result<TableListResult, BaseError>
where
E: RelationBatchExecutor,
{
let page = self.query.paginate_records().await?;
let relations = self.relation_loader.load(&page.data, executor).await?;
Ok(TableListResult { page, relations })
}
}
fn value_key(value: &Value) -> String {
serde_json::to_string(value).unwrap_or_else(|_| "null".to_string())
}
enum TreeBuildFrame {
Enter { index: usize, depth: usize },
Leave { index: usize },
}
fn work_stack_error() -> BaseError {
BaseError::ConfigError("树构建工作栈与结果不符".to_string())
}
#[cfg(test)]
mod tests {
use super::*;
fn linear_chain(len: usize) -> Vec<Record> {
(0..len)
.map(|index| {
Record::new().set("id", index).set(
"parent_id",
if index == 0 {
Value::Null
} else {
serde_json::json!(index - 1)
},
)
})
.collect()
}
fn chain_depth(tree: &[TableTreeNode]) -> usize {
let mut depth = 0;
let mut cursor = tree.first();
while let Some(node) = cursor {
depth += 1;
cursor = node.children.first();
}
depth
}
#[test]
fn tree_node_cap_rejects_overflow() {
ensure_tree_node_cap(DEFAULT_TREE_MAX_NODES, DEFAULT_TREE_MAX_NODES)
.expect("节点数等于上限应放行");
ensure_tree_node_cap(3, 10).expect("节点数低于上限应放行");
let error = ensure_tree_node_cap(DEFAULT_TREE_MAX_NODES + 1, DEFAULT_TREE_MAX_NODES)
.expect_err("节点数超过上限必须报错");
assert!(
matches!(error, BaseError::ParamInvalid(_, _)),
"树节点超限应返回 ParamInvalid: {error:?}"
);
let error = ensure_tree_node_cap(11, 10).expect_err("自定义上限超限必须报错");
assert!(matches!(error, BaseError::ParamInvalid(_, _)));
}
#[test]
fn tree_builder_keeps_order_and_nests_children() {
let rows = vec![
Record::new().set("id", 1).set("parent_id", Value::Null),
Record::new().set("id", 2).set("parent_id", 1),
];
let tree = Tables::build_tree(rows, "id", "parent_id").expect("树关系应有效");
assert_eq!(tree.len(), 1);
assert_eq!(tree[0].children.len(), 1);
assert_eq!(
tree[0].children[0].record.get("id"),
Some(&serde_json::json!(2))
);
}
#[test]
fn tree_builder_rejects_null_and_duplicate_ids() {
let null_id = Tables::build_tree(
vec![Record::new()
.set("id", Value::Null)
.set("parent_id", Value::Null)],
"id",
"parent_id",
)
.expect_err("null 主键必须失败");
assert!(matches!(null_id, BaseError::ParamInvalid(_, _)));
let duplicate = Tables::build_tree(
vec![
Record::new().set("id", 1).set("parent_id", Value::Null),
Record::new().set("id", 1).set("parent_id", Value::Null),
],
"id",
"parent_id",
)
.expect_err("重复主键必须失败");
assert!(matches!(duplicate, BaseError::ConfigError(_)));
}
#[test]
fn tree_depth_cap_rejects_overflow() {
ensure_tree_depth_cap(DEFAULT_TREE_MAX_DEPTH, DEFAULT_TREE_MAX_DEPTH)
.expect("深度等于上限应放行");
ensure_tree_depth_cap(3, 10).expect("深度低于上限应放行");
let error = ensure_tree_depth_cap(DEFAULT_TREE_MAX_DEPTH + 1, DEFAULT_TREE_MAX_DEPTH)
.expect_err("深度超过上限必须报错");
assert!(
matches!(error, BaseError::ParamInvalid(_, _)),
"树深度超限应返回 ParamInvalid: {error:?}"
);
}
#[test]
fn tree_builder_rejects_linear_chain_deeper_than_cap() {
let error = Tables::build_tree(linear_chain(2_000), "id", "parent_id")
.expect_err("超深线性链必须报错而不是爆栈");
assert!(
matches!(error, BaseError::ParamInvalid(_, _)),
"超深线性链应返回 ParamInvalid: {error:?}"
);
}
#[test]
fn tree_builder_accepts_linear_chain_at_depth_cap() {
let tree = Tables::build_tree(linear_chain(DEFAULT_TREE_MAX_DEPTH), "id", "parent_id")
.expect("等于深度上限的线性链应组装成功");
assert_eq!(tree.len(), 1, "线性链只应有一个根节点");
assert_eq!(chain_depth(&tree), DEFAULT_TREE_MAX_DEPTH);
}
#[test]
fn tree_builder_rejects_cycles_without_roots() {
let cycle = Tables::build_tree(
vec![
Record::new().set("id", 1).set("parent_id", 2),
Record::new().set("id", 2).set("parent_id", 1),
],
"id",
"parent_id",
)
.expect_err("无根循环必须失败");
assert!(matches!(cycle, BaseError::ConfigError(_)));
}
}