1use crate::plan::{CommandPlan, CtePlan, CtePlanBody, QueryPlan, RelationalPlan, SourcePlan};
10use crate::SQLError;
11use std::collections::{BTreeMap, BTreeSet};
12
13pub fn cte_reference_name(reference: &str) -> Option<String> {
15 let (schema, name) = crate::RelationIdentity::parse_reference(reference).ok()?;
16 schema.is_none().then_some(name)
17}
18
19pub fn reachable_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
20 let targets = plan
21 .ctes
22 .iter()
23 .map(|cte| cte.name.clone())
24 .collect::<BTreeSet<_>>();
25 if targets.is_empty() {
26 return BTreeSet::new();
27 }
28
29 let mut reachable = plan
30 .ctes
31 .iter()
32 .filter(|cte| cte.body.modifies_data())
33 .map(|cte| cte.name.clone())
34 .collect::<BTreeSet<_>>();
35 collect_target_cte_references_from_root(&plan.root, &targets, &BTreeSet::new(), &mut reachable);
36
37 let mut expanded = BTreeSet::new();
38 loop {
39 let pending = plan
40 .ctes
41 .iter()
42 .enumerate()
43 .filter(|(_, cte)| reachable.contains(&cte.name) && !expanded.contains(&cte.name))
44 .collect::<Vec<_>>();
45 if pending.is_empty() {
46 break;
47 }
48 for (index, cte) in pending {
49 expanded.insert(cte.name.clone());
50 let visible_dependencies = if cte.recursive {
51 targets.clone()
52 } else {
53 plan.ctes[..index]
54 .iter()
55 .map(|dependency| dependency.name.clone())
56 .collect::<BTreeSet<_>>()
57 };
58 collect_target_cte_references_from_body(
59 &cte.body,
60 &visible_dependencies,
61 &BTreeSet::new(),
62 &mut reachable,
63 );
64 }
65 }
66 reachable
67}
68
69pub fn cte_definition_references(ctes: &[CtePlan], index: usize) -> BTreeSet<String> {
71 let cte = &ctes[index];
72 let visible = if cte.recursive {
73 ctes.iter()
74 } else {
75 ctes[..index].iter()
76 }
77 .map(|cte| cte.name.clone())
78 .collect::<BTreeSet<_>>();
79 let mut references = BTreeSet::new();
80 collect_target_cte_references_from_body(&cte.body, &visible, &BTreeSet::new(), &mut references);
81 references
82}
83
84pub fn primary_query_cte_references(plan: &QueryPlan) -> BTreeSet<String> {
86 let targets = plan
87 .ctes
88 .iter()
89 .map(|cte| cte.name.clone())
90 .collect::<BTreeSet<_>>();
91 let mut references = BTreeSet::new();
92 if !targets.is_empty() {
93 collect_target_cte_references_from_root(
94 &plan.root,
95 &targets,
96 &BTreeSet::new(),
97 &mut references,
98 );
99 }
100 references
101}
102
103pub fn primary_command_cte_references(
105 ctes: &[CtePlan],
106 queries: &[&QueryPlan],
107 source: Option<&SourcePlan>,
108) -> BTreeSet<String> {
109 let targets = ctes
110 .iter()
111 .map(|cte| cte.name.clone())
112 .collect::<BTreeSet<_>>();
113 let mut references = BTreeSet::new();
114 if targets.is_empty() {
115 return references;
116 }
117 for query in queries {
118 collect_target_cte_references_from_nested_query(
119 query,
120 &targets,
121 &BTreeSet::new(),
122 &mut references,
123 );
124 }
125 if let Some(source) = source {
126 collect_target_cte_references_from_source(
127 source,
128 &targets,
129 &BTreeSet::new(),
130 &mut references,
131 );
132 }
133 references
134}
135
136pub fn cte_references_own_name(cte: &CtePlan) -> bool {
137 let targets = BTreeSet::from([cte.name.clone()]);
138 let mut references = BTreeSet::new();
139 collect_target_cte_references_from_body(&cte.body, &targets, &BTreeSet::new(), &mut references);
140 references.contains(&cte.name)
141}
142
143pub fn ordered_plan_ctes(plan: &QueryPlan) -> Result<Vec<&CtePlan>, SQLError> {
144 ordered_cte_plans(&plan.ctes)
145}
146
147pub fn ordered_cte_plans(ctes: &[CtePlan]) -> Result<Vec<&CtePlan>, SQLError> {
148 order_cte_plans(ctes.iter().collect())
149}
150
151pub fn order_cte_plans(plans: Vec<&CtePlan>) -> Result<Vec<&CtePlan>, SQLError> {
152 if !plans.iter().any(|cte| cte.recursive) {
153 return Ok(plans);
154 }
155 let targets = plans
156 .iter()
157 .map(|cte| cte.name.clone())
158 .collect::<BTreeSet<_>>();
159 let dependencies = plans
160 .iter()
161 .map(|cte| {
162 let mut references = BTreeSet::new();
163 collect_target_cte_references_from_body(
164 &cte.body,
165 &targets,
166 &BTreeSet::new(),
167 &mut references,
168 );
169 references.remove(&cte.name);
170 references
171 })
172 .collect::<Vec<_>>();
173 let mut emitted = BTreeSet::new();
174 let mut ordered = Vec::with_capacity(plans.len());
175 let mut remaining = (0..plans.len()).collect::<BTreeSet<_>>();
176 while !remaining.is_empty() {
177 let ready = remaining
178 .iter()
179 .copied()
180 .find(|index| dependencies[*index].is_subset(&emitted));
181 let Some(index) = ready else {
182 return Err(SQLError::Routine {
183 sqlstate: "0A000".into(),
184 message: "mutual recursion between WITH items is not implemented".into(),
185 });
186 };
187 remaining.remove(&index);
188 emitted.insert(plans[index].name.clone());
189 ordered.push(plans[index]);
190 }
191 Ok(ordered)
192}
193
194pub fn single_reference_plan_cte_names(plan: &QueryPlan) -> BTreeSet<String> {
196 let targets = plan
197 .ctes
198 .iter()
199 .map(|cte| cte.name.clone())
200 .collect::<BTreeSet<_>>();
201 let mut counts = targets
202 .iter()
203 .map(|name| (name.clone(), 0usize))
204 .collect::<BTreeMap<_, _>>();
205 count_plan_cte_references(plan, &targets, &mut counts);
206 counts
207 .into_iter()
208 .filter_map(|(name, count)| (count == 1).then_some(name))
209 .collect()
210}
211
212fn count_plan_cte_references(
213 plan: &QueryPlan,
214 targets: &BTreeSet<String>,
215 counts: &mut BTreeMap<String, usize>,
216) {
217 for cte in &plan.ctes {
218 count_cte_body_references(&cte.body, targets, counts);
219 }
220 count_relational_cte_references(&plan.root, targets, counts);
221}
222
223fn count_cte_body_references(
224 body: &CtePlanBody,
225 targets: &BTreeSet<String>,
226 counts: &mut BTreeMap<String, usize>,
227) {
228 match body {
229 CtePlanBody::Query(query) => count_plan_cte_references(query, targets, counts),
230 CtePlanBody::Command(command) => {
231 for cte in command.ctes() {
232 count_cte_body_references(&cte.body, targets, counts);
233 }
234 for query in command.query_inputs() {
235 count_plan_cte_references(query, targets, counts);
236 }
237 if let Some(source) = command.source_input() {
238 count_source_cte_references(source, targets, counts);
239 }
240 }
241 }
242}
243
244fn count_relational_cte_references(
245 plan: &RelationalPlan,
246 targets: &BTreeSet<String>,
247 counts: &mut BTreeMap<String, usize>,
248) {
249 match plan {
250 RelationalPlan::QueryBlock(block) => {
251 if let Some(source) = &block.from {
252 count_source_cte_references(source, targets, counts);
253 }
254 for subquery in &block.subqueries {
255 count_plan_cte_references(subquery, targets, counts);
256 }
257 }
258 RelationalPlan::SetOp {
259 left,
260 right,
261 subqueries,
262 ..
263 } => {
264 count_plan_cte_references(left, targets, counts);
265 count_plan_cte_references(right, targets, counts);
266 for subquery in subqueries {
267 count_plan_cte_references(subquery, targets, counts);
268 }
269 }
270 RelationalPlan::Values { subqueries, .. } => {
271 for subquery in subqueries {
272 count_plan_cte_references(subquery, targets, counts);
273 }
274 }
275 }
276}
277
278fn count_source_cte_references(
279 source: &SourcePlan,
280 targets: &BTreeSet<String>,
281 counts: &mut BTreeMap<String, usize>,
282) {
283 match source {
284 crate::plan::SourcePlan::RetainedRows(_) => {}
285 SourcePlan::Table { name, .. } => {
286 if let Some(name) = cte_reference_name(name).filter(|name| targets.contains(name)) {
287 *counts.entry(name).or_default() += 1;
288 }
289 }
290 SourcePlan::Join { left, right, .. } => {
291 count_source_cte_references(left, targets, counts);
292 count_source_cte_references(right, targets, counts);
293 }
294 SourcePlan::Subquery { body, .. } => {
295 count_plan_cte_references(body, targets, counts);
296 }
297 SourcePlan::Values { .. }
298 | SourcePlan::Function { .. }
299 | SourcePlan::FunctionGroup { .. } => {}
300 }
301}
302
303fn collect_target_cte_references_from_root(
304 root: &RelationalPlan,
305 targets: &BTreeSet<String>,
306 shadowed: &BTreeSet<String>,
307 references: &mut BTreeSet<String>,
308) {
309 match root {
310 RelationalPlan::QueryBlock(block) => {
311 if let Some(source) = &block.from {
312 collect_target_cte_references_from_source(source, targets, shadowed, references);
313 }
314 for subquery in &block.subqueries {
315 collect_target_cte_references_from_nested_query(
316 subquery, targets, shadowed, references,
317 );
318 }
319 }
320 RelationalPlan::SetOp {
321 left,
322 right,
323 subqueries,
324 ..
325 } => {
326 collect_target_cte_references_from_nested_query(left, targets, shadowed, references);
327 collect_target_cte_references_from_nested_query(right, targets, shadowed, references);
328 for subquery in subqueries {
329 collect_target_cte_references_from_nested_query(
330 subquery, targets, shadowed, references,
331 );
332 }
333 }
334 RelationalPlan::Values { subqueries, .. } => {
335 for subquery in subqueries {
336 collect_target_cte_references_from_nested_query(
337 subquery, targets, shadowed, references,
338 );
339 }
340 }
341 }
342}
343
344fn collect_target_cte_references_from_source(
345 source: &SourcePlan,
346 targets: &BTreeSet<String>,
347 shadowed: &BTreeSet<String>,
348 references: &mut BTreeSet<String>,
349) {
350 match source {
351 crate::plan::SourcePlan::RetainedRows(_) => {}
352 SourcePlan::Table { name, .. } => {
353 if let Some(name) = cte_reference_name(name)
354 .filter(|name| targets.contains(name) && !shadowed.contains(name))
355 {
356 references.insert(name);
357 }
358 }
359 SourcePlan::Join { left, right, .. } => {
360 collect_target_cte_references_from_source(left, targets, shadowed, references);
361 collect_target_cte_references_from_source(right, targets, shadowed, references);
362 }
363 SourcePlan::Subquery { body, .. } => {
364 collect_target_cte_references_from_nested_query(body, targets, shadowed, references);
365 }
366 SourcePlan::Values { .. }
367 | SourcePlan::Function { .. }
368 | SourcePlan::FunctionGroup { .. } => {}
369 }
370}
371
372fn collect_target_cte_references_from_command_root(
373 command: &CommandPlan,
374 targets: &BTreeSet<String>,
375 shadowed: &BTreeSet<String>,
376 references: &mut BTreeSet<String>,
377) {
378 for query in command.query_inputs() {
379 collect_target_cte_references_from_nested_query(query, targets, shadowed, references);
380 }
381 if let Some(source) = command.source_input() {
382 collect_target_cte_references_from_source(source, targets, shadowed, references);
383 }
384}
385
386fn collect_target_cte_references_from_body(
387 body: &CtePlanBody,
388 targets: &BTreeSet<String>,
389 shadowed: &BTreeSet<String>,
390 references: &mut BTreeSet<String>,
391) {
392 let CtePlanBody::Command(command) = body else {
393 if let CtePlanBody::Query(query) = body {
394 collect_target_cte_references_from_nested_query(query, targets, shadowed, references);
395 }
396 return;
397 };
398 let locals = command
399 .ctes()
400 .iter()
401 .map(|cte| cte.name.clone())
402 .collect::<BTreeSet<_>>();
403 let mut reachable = command
404 .ctes()
405 .iter()
406 .filter(|cte| cte.body.modifies_data())
407 .map(|cte| cte.name.clone())
408 .collect::<BTreeSet<_>>();
409 collect_target_cte_references_from_command_root(
410 command,
411 &locals,
412 &BTreeSet::new(),
413 &mut reachable,
414 );
415 let mut expanded = BTreeSet::new();
416 loop {
417 let pending = command
418 .ctes()
419 .iter()
420 .enumerate()
421 .filter(|(_, cte)| reachable.contains(&cte.name) && !expanded.contains(&cte.name))
422 .collect::<Vec<_>>();
423 if pending.is_empty() {
424 break;
425 }
426 for (index, cte) in pending {
427 expanded.insert(cte.name.clone());
428 let visible = if cte.recursive {
429 locals.clone()
430 } else {
431 command.ctes()[..index]
432 .iter()
433 .map(|cte| cte.name.clone())
434 .collect()
435 };
436 collect_target_cte_references_from_body(
437 &cte.body,
438 &visible,
439 &BTreeSet::new(),
440 &mut reachable,
441 );
442 }
443 }
444 let mut root_shadowed = shadowed.clone();
445 root_shadowed.extend(locals.iter().cloned());
446 collect_target_cte_references_from_command_root(command, targets, &root_shadowed, references);
447 let mut preceding = shadowed.clone();
448 for cte in command.ctes() {
449 if reachable.contains(&cte.name) {
450 let definition = if cte.recursive {
451 shadowed.union(&locals).cloned().collect()
452 } else {
453 preceding.clone()
454 };
455 collect_target_cte_references_from_body(&cte.body, targets, &definition, references);
456 }
457 preceding.insert(cte.name.clone());
458 }
459}
460
461fn collect_target_cte_references_from_nested_query(
462 plan: &QueryPlan,
463 targets: &BTreeSet<String>,
464 shadowed: &BTreeSet<String>,
465 references: &mut BTreeSet<String>,
466) {
467 let local_reachable = reachable_plan_cte_names(plan);
468 let mut root_shadowed = shadowed.clone();
469 root_shadowed.extend(
470 plan.ctes
471 .iter()
472 .map(|cte| cte.name.clone())
473 .filter(|name| targets.contains(name)),
474 );
475 collect_target_cte_references_from_root(&plan.root, targets, &root_shadowed, references);
476 let recursive_scope = plan.ctes.iter().any(|cte| cte.recursive).then(|| {
477 plan.ctes
478 .iter()
479 .map(|cte| cte.name.clone())
480 .collect::<BTreeSet<_>>()
481 });
482 let mut preceding = BTreeSet::new();
483 for cte in &plan.ctes {
484 if local_reachable.contains(&cte.name) {
485 let mut definition_shadowed = shadowed.clone();
486 if let Some(recursive_scope) = recursive_scope.as_ref() {
487 definition_shadowed.extend(
488 recursive_scope
489 .iter()
490 .filter(|name| targets.contains(*name))
491 .cloned(),
492 );
493 } else {
494 definition_shadowed.extend(
495 preceding
496 .iter()
497 .filter(|name| targets.contains(*name))
498 .cloned(),
499 );
500 }
501 collect_target_cte_references_from_body(
502 &cte.body,
503 targets,
504 &definition_shadowed,
505 references,
506 );
507 }
508 preceding.insert(cte.name.clone());
509 }
510}