uqa_sql/catalog/dependencies/
graph.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! The dependencies of one catalog snapshot, indexed as `pg_depend`'s two indexes are: by the depending object and by the referenced object.
8
9use super::{Dependency, ObjectAddress};
10use std::collections::BTreeMap;
11
12#[derive(Debug, Clone, Default)]
13pub struct DependencyGraph {
14    edges: Vec<Dependency>,
15    by_dependent: BTreeMap<(u32, u32), Vec<usize>>,
16    by_referenced: BTreeMap<(u32, u32), Vec<usize>>,
17}
18
19impl DependencyGraph {
20    /// Index the dependencies in the order they were recorded. `pg_depend` keeps a dependency that two recordings of one object share, such as a routine's argument type that its body names again, and the deletion search visits the object once either way.
21    pub fn new(edges: impl IntoIterator<Item = Dependency>) -> Self {
22        let edges = edges.into_iter().collect::<Vec<_>>();
23        let mut by_dependent: BTreeMap<(u32, u32), Vec<usize>> = BTreeMap::new();
24        let mut by_referenced: BTreeMap<(u32, u32), Vec<usize>> = BTreeMap::new();
25        for (index, edge) in edges.iter().enumerate() {
26            by_dependent
27                .entry((edge.dependent.class_id, edge.dependent.object_id))
28                .or_default()
29                .push(index);
30            by_referenced
31                .entry((edge.referenced.class_id, edge.referenced.object_id))
32                .or_default()
33                .push(index);
34        }
35        // `pg_depend`'s indexes order the rows of one object by column number, then as they were stored.
36        for rows in by_dependent.values_mut() {
37            rows.sort_by_key(|index| edges[*index].dependent.sub_id);
38        }
39        for rows in by_referenced.values_mut() {
40            rows.sort_by_key(|index| edges[*index].referenced.sub_id);
41        }
42        Self {
43            edges,
44            by_dependent,
45            by_referenced,
46        }
47    }
48
49    pub fn edges(&self) -> &[Dependency] {
50        &self.edges
51    }
52
53    /// What `object` depends on; for a whole object, what any of its columns depends on too.
54    pub fn references_of(&self, object: ObjectAddress) -> impl Iterator<Item = &Dependency> {
55        self.by_dependent
56            .get(&(object.class_id, object.object_id))
57            .into_iter()
58            .flatten()
59            .map(|index| &self.edges[*index])
60            .filter(move |edge| object.sub_id == 0 || edge.dependent.sub_id == object.sub_id)
61    }
62
63    /// What depends on `object`; for a whole object, what depends on any of its columns too.
64    pub fn dependents_of(&self, object: ObjectAddress) -> impl Iterator<Item = &Dependency> {
65        self.by_referenced
66            .get(&(object.class_id, object.object_id))
67            .into_iter()
68            .flatten()
69            .map(|index| &self.edges[*index])
70            .filter(move |edge| object.sub_id == 0 || edge.referenced.sub_id == object.sub_id)
71    }
72}
uqa_sql/catalog/dependencies/graph.rs

uqa_sql/catalog/dependencies/
graph.rs
