我们经常会遇到这样的场景，知道程序的入口A，然后A调用XX，XX调用XXX……，最后XN调用D,我们只知道A和D，想要找到这个调用链，比如
A-B-C-D
但是很多情况不是像这样的链表或者树，而是调用很复杂的图。如下图
?
?为了模拟这个调用链，我们可以创建5个测试包。
CREATE OR REPLACE PACKAGE cux_test_d IS
PROCEDURE test;
END cux_test_d;
CREATE OR REPLACE PACKAGE BODY cux_test_d IS
PROCEDURE test IS
BEGIN
NULL;
END;
END cux_test_d;
CREATE OR REPLACE PACKAGE cux_test_c IS
PROCEDURE test;
END cux_test_c;
CREATE OR REPLACE PACKAGE BODY cux_test_c IS
PROCEDURE test IS
BEGIN
cux_test_d.test;
END;
END cux_test_c;
CREATE OR REPLACE PACKAGE cux_test_b IS
PROCEDURE test;
END cux_test_b;
CREATE OR REPLACE PACKAGE BODY cux_test_b IS
PROCEDURE test IS
BEGIN
cux_test_c.test;
END;
END cux_test_b;
CREATE OR REPLACE PACKAGE cux_test_e IS
PROCEDURE test;
END cux_test_e;
CREATE OR REPLACE PACKAGE BODY cux_test_e IS
PROCEDURE test IS
BEGIN
cux_test_d.test;
END;
END cux_test_e;
CREATE OR REPLACE PACKAGE cux_test_a IS
PROCEDURE test_1;
PROCEDURE test_2;
END cux_test_a;
CREATE OR REPLACE PACKAGE BODY cux_test_a IS
PROCEDURE test_1 IS
BEGIN
cux_test_e.test;
END;
PROCEDURE test_2 IS
BEGIN
cux_test_b.test;
END;
END cux_test_a;
而这个依赖关系，用视图all_dependencies提现，如下：
（可能存在更好的调用视图，我只找到了这个）
?这里有两点需要注意的地方
1.REFERENCED_NAME具有索引，而NAME不具有
2.Package Body CUX_TEST_C 调用了Package CUX_TEST_D,但是CUX_TEST_D的调用链仍旧是 Package Body调用其它，所以我们在处理的时候，需要把Package和Package Body当成同一个东西，我这里是都当成package 处理
而针对第一点，需要将我们的图变成下列形式(否则，用NAME查找下一个REFERENCED_NAME，没有索引了，所有查询都是全表扫描)
?因为从D找到C比较容易，而C找D比较难
仿照JavaScript数据结构-7-2图深度优先搜索_香辣素毛肚的博客-CSDN博客
在我们编写递归的深度优先搜索方法，我们需要创建一个栈的数据结构
先创建一个数组对象
create or replace type cux_items_type is table of varchar2(4000);
然后编写我们的栈对象
CREATE OR REPLACE TYPE cux_stack_type AS OBJECT
(
top NUMBER,
items cux_items_type,
MEMBER PROCEDURE init(SELF IN OUT cux_stack_type),
MEMBER FUNCTION is_empty RETURN BOOLEAN,
MEMBER PROCEDURE push(SELF IN OUT cux_stack_type
,p_value IN VARCHAR2),
MEMBER FUNCTION pop(SELF IN OUT cux_stack_type
,p_value OUT VARCHAR2) RETURN BOOLEAN
)
CREATE OR REPLACE TYPE BODY cux_stack_type IS
MEMBER PROCEDURE init(SELF IN OUT cux_stack_type) IS
BEGIN
self.top := 0;
self.items := cux_items_type();
END;
MEMBER FUNCTION is_empty RETURN BOOLEAN IS
BEGIN
--PLSQL数组下标为1开始
IF self.top = 0
THEN
RETURN TRUE;
ELSE
RETURN FALSE;
END IF;
END is_empty;
MEMBER PROCEDURE push(SELF IN OUT cux_stack_type
,p_value IN VARCHAR2) IS
BEGIN
--可变长数组，不用考虑栈满
self.top := self.top + 1;
self.items.extend;
self.items(self.top) := p_value;
END push;
MEMBER FUNCTION pop(SELF IN OUT cux_stack_type
,p_value OUT VARCHAR2) RETURN BOOLEAN IS
BEGIN
IF self.top = 0
THEN
RETURN FALSE; --栈空
ELSE
p_value := self.items(self.top);
self.top := self.top - 1;
RETURN TRUE;
END IF;
END pop;
END;
测试一下
DECLARE
stack cux_stack_type;
l_boolean BOOLEAN;
l_value VARCHAR2(240);
BEGIN
stack := NEW cux_stack_type(0
,NULL);
stack.init;
stack.push(1);
stack.push(2);
stack.push(3);
l_boolean := stack.pop(l_value);
dbms_output.put_line(l_value);
l_boolean := stack.pop(l_value);
dbms_output.put_line(l_value);
l_boolean := stack.pop(l_value);
dbms_output.put_line(l_value);
l_boolean := stack.pop(l_value);
dbms_output.put_line(l_value);
IF NOT l_boolean
THEN
dbms_output.put_line('栈空');
END IF;
END;
?现在可以开始DFS遍历了
创建视图
CREATE OR REPLACE VIEW CUX_ALL_DEPENDENCIES_V AS
SELECT "OWNER"
,"NAME"
,"TYPE"
,"REFERENCED_OWNER"
,"REFERENCED_NAME"
,"REFERENCED_TYPE"
,"REFERENCED_LINK_NAME"
,"DEPENDENCY_TYPE"
FROM (SELECT owner
,NAME
,CASE
WHEN TYPE IN ('PACKAGE BODY'
,'PACKAGE') THEN
'PACKAGE'
ELSE
TYPE
END TYPE
,referenced_owner
,referenced_name
,CASE
WHEN referenced_type IN ('PACKAGE BODY'
,'PACKAGE') THEN
'PACKAGE'
ELSE
referenced_type
END referenced_type
,referenced_link_name
,dependency_type
FROM all_dependencies)
WHERE 1 = 1
AND NOT (referenced_name = NAME AND referenced_type = TYPE AND
referenced_owner = owner);
使package body=package
创建程序包
CREATE OR REPLACE PACKAGE cux_util_pub IS
TYPE stacks_tbl IS TABLE OF cux_stack_type INDEX BY BINARY_INTEGER;
PROCEDURE find_dependencies(p_start_name IN VARCHAR2
,p_start_type IN VARCHAR2
,p_start_owner IN VARCHAR2
,p_end_name IN VARCHAR2
,p_end_type IN VARCHAR2
,p_end_owner IN VARCHAR2
,p_status_code OUT VARCHAR2
,p_msg OUT VARCHAR2
,p_stacks_tbl OUT stacks_tbl);
PROCEDURE find_all_path(p_start_object_id IN NUMBER
,p_end_object_id IN NUMBER
,p_stack IN OUT NOCOPY cux_stack_type
,d IN OUT NUMBER
,p_stacks_tbl IN OUT NOCOPY stacks_tbl
);
END cux_util_pub;
CREATE OR REPLACE PACKAGE BODY cux_util_pub IS
--采用递归形式的深度优先搜索，可能会导致栈溢出，后期优化
PROCEDURE find_dependencies(p_start_name IN VARCHAR2
,p_start_type IN VARCHAR2
,p_start_owner IN VARCHAR2
,p_end_name IN VARCHAR2
,p_end_type IN VARCHAR2
,p_end_owner IN VARCHAR2
,p_status_code OUT VARCHAR2
,p_msg OUT VARCHAR2
,p_stacks_tbl OUT stacks_tbl) IS
l_start_object_id NUMBER;
l_end_object_id NUMBER;
-- l_path_tbl path_tbl;
d NUMBER := -1;
l_start_type VARCHAR2(240);
l_end_type VARCHAR2(240);
l_stack cux_stack_type;
BEGIN
--g_paths_tbl.delete;
l_stack := NEW cux_stack_type(0
,NULL);
l_stack.init;
l_start_type:=p_start_type;
l_end_type:=p_end_type;
IF p_start_type LIKE 'PACKAGE%'
THEN
l_start_type := 'PACKAGE';
END IF;
IF p_end_type LIKE 'PACKAGE%'
THEN
l_end_type := 'PACKAGE';
END IF;
BEGIN
SELECT d.object_id
INTO l_start_object_id
FROM sys.dba_objects d
WHERE d.object_name = p_start_name
AND d.object_type = l_start_type
AND d.owner = p_start_owner;
EXCEPTION
WHEN OTHERS THEN
p_status_code := 'E';
p_msg := '参数错误';
return;
END;
BEGIN
SELECT d.object_id
INTO l_end_object_id
FROM dba_objects d
WHERE d.object_name = p_end_name
AND d.object_type = l_end_type
AND d.owner = p_end_owner;
EXCEPTION
WHEN OTHERS THEN
p_status_code := 'E';
p_msg := '参数错误';
return;
END;
find_all_path(p_start_object_id => l_start_object_id
,p_end_object_id => l_end_object_id
,p_stack => l_stack
,d => d
,p_stacks_tbl => p_stacks_tbl);
p_status_code := 'S';
END find_dependencies;
--获取该顶点第一个边表
FUNCTION get_first_starc(p_object_id IN NUMBER) RETURN NUMBER IS
l_start_object_name VARCHAR2(240);
l_start_object_type VARCHAR2(240);
l_start_object_owner VARCHAR2(240);
l_next_object_name VARCHAR2(240);
l_next_object_type VARCHAR2(240);
l_next_object_owner VARCHAR2(240);
l_object_id NUMBER;
BEGIN
SELECT d.object_name
,d.object_type
,d.owner
INTO l_start_object_name
,l_start_object_type
,l_start_object_owner
FROM dba_objects d
WHERE d.object_id = p_object_id;
/* IF l_start_object_type LIKE 'PACKAGE' || '%'
THEN
--忽略package和package body区别
l_start_object_type := 'PACKAGE';
END IF;*/
--没有链表，只能使用排序找下一个
BEGIN
SELECT NAME
,owner
,TYPE
INTO l_next_object_name
,l_next_object_owner
,l_next_object_type
FROM (SELECT a.name
,a.owner
,a.type
,row_number() over(PARTITION BY 1 ORDER BY a.owner, a.name, a.type) row_number
FROM cux_all_dependencies_v a
WHERE a.referenced_owner = l_start_object_owner
AND a.referenced_name = l_start_object_name
AND a.referenced_type LIKE l_start_object_type)
WHERE row_number = 1;
EXCEPTION
WHEN OTHERS THEN
RETURN NULL;
END;
/* IF l_next_object_type LIKE 'PACKAGE' || '%'
THEN
--忽略package和package body区别
l_next_object_type := 'PACKAGE';
END IF;
*/
SELECT d.object_id
INTO l_object_id
FROM dba_objects d
WHERE d.owner = l_next_object_owner
AND d.object_name = l_next_object_name
AND d.object_type = l_next_object_type;
RETURN l_object_id;
END get_first_starc;
FUNCTION get_next_starc(p_parent_object_id IN NUMBER
,p_son_object_id IN NUMBER) RETURN NUMBER IS
l_start_object_name VARCHAR2(240);
l_start_object_type VARCHAR2(240);
l_start_object_owner VARCHAR2(240);
l_next_object_name VARCHAR2(240);
l_next_object_type VARCHAR2(240);
l_next_object_owner VARCHAR2(240);
l_object_id NUMBER;
l_son_object_name VARCHAR2(240);
l_son_object_type VARCHAR2(240);
l_son_object_owner VARCHAR2(240);
l_row_number NUMBER;
BEGIN
SELECT d.object_name
,d.object_type
,d.owner
INTO l_start_object_name
,l_start_object_type
,l_start_object_owner
FROM dba_objects d
WHERE d.object_id = p_parent_object_id;
/* IF l_start_object_type LIKE 'PACKAGE' || '%'
THEN
--忽略package和package body区别
l_start_object_type := 'PACKAGE';
END IF;*/
SELECT d.object_name
,d.object_type
,d.owner
INTO l_son_object_name
,l_son_object_type
,l_son_object_owner
FROM dba_objects d
WHERE d.object_id = p_son_object_id;
BEGIN
SELECT row_number
INTO l_row_number
FROM (SELECT a.name
,a.owner
,a.type
,row_number() over(PARTITION BY 1 ORDER BY a.owner, a.name, a.type) row_number
FROM cux_all_dependencies_v a
WHERE a.referenced_owner = l_start_object_owner
AND a.referenced_name = l_start_object_name
AND a.referenced_type = l_start_object_type)
WHERE NAME = l_son_object_name
AND owner = l_son_object_owner
AND TYPE = l_son_object_type;
EXCEPTION
WHEN OTHERS THEN
RETURN NULL;
END;
BEGIN
SELECT NAME
,owner
,TYPE
INTO l_next_object_name
,l_next_object_owner
,l_next_object_type
FROM (SELECT a.name
,a.owner
,a.type
,row_number() over(PARTITION BY 1 ORDER BY a.owner, a.name, a.type) row_number
FROM cux_all_dependencies_v a
WHERE a.referenced_owner = l_start_object_owner
AND a.referenced_name = l_start_object_name
AND a.referenced_type = l_start_object_type)
WHERE row_number = l_row_number + 1;
EXCEPTION
WHEN OTHERS THEN
RETURN NULL;
END;
SELECT d.object_id
INTO l_object_id
FROM dba_objects d
WHERE d.owner = l_next_object_owner
AND d.object_name = l_next_object_name
AND d.object_type = l_next_object_type;
RETURN l_object_id;
END get_next_starc;
PROCEDURE print_stack_name(p_stack IN cux_stack_type) IS
l_info VARCHAR2(4000);
BEGIN
IF p_stack.top <> 0
THEN
FOR i IN 1..p_stack.top
LOOP
BEGIN
SELECT d.owner || '.' || d.object_name || '(' || d.object_type || ')'
INTO l_info
FROM dba_objects d
WHERE d.object_id = p_stack.items(i);
dbms_output.put(l_info || '->');
EXCEPTION
WHEN OTHERS THEN
NULL;
END;
END LOOP;
dbms_output.new_line;
END IF;
END print_stack_name;
--BFS
--package和package body 统一取package的 object_id
PROCEDURE find_all_path(p_start_object_id IN NUMBER
,p_end_object_id IN NUMBER
,p_stack IN OUT NOCOPY cux_stack_type
,d IN OUT NUMBER
,p_stacks_tbl IN OUT NOCOPY stacks_tbl) IS
-- d NUMBER := -1; --路径长度
-- l_path_tbl path_tbl; --路径数组
TYPE hash_map IS TABLE OF NUMBER INDEX BY VARCHAR2(240);
l_visited hash_map; --类似键值对，该节点是否已被访问
--
-- l_paths_tbl paths_tbl; --记录所有类型数组
p NUMBER;
w NUMBER;
l_current_index NUMBER;
l_visited_result NUMBER;
l_pop_boolean BOOLEAN;
l_value VARCHAR2(4000);
BEGIN
d := d + 1;
-- p_path_tbl(d) := p_start_object_id;
--入栈
p_stack.push(p_start_object_id);
l_visited(p_start_object_id) := 1;
IF p_start_object_id = p_end_object_id
THEN
--当p_start_object_id_n=p_end_object_id 则表示找到了A-B路径
--写入二维数组
--数组实现不了，只能写入栈里了
-- g_paths_tbl(g_paths_tbl.count) := p_path_tbl;
-- print_object_name(p_path_tbl => p_path_tbl);
--出栈
p_stacks_tbl(p_stacks_tbl.count) := p_stack;
l_pop_boolean := p_stack.pop(l_value);
print_stack_name(p_stack=>p_stack);
--p_path_tbl.DELETE;
END IF;
--p指向p_start_object_id的第一个临点
p := get_first_starc(p_object_id => p_start_object_id);
WHILE (p IS NOT NULL)
LOOP
w := p;
BEGIN
l_visited_result := l_visited(w);
EXCEPTION
WHEN OTHERS THEN
l_visited_result := 0;
END;
IF l_visited_result = 0
THEN
--该节点未访问过
find_all_path(w
,p_end_object_id
,p_stack
,d
,p_stacks_tbl);
p := get_next_starc(p_start_object_id
,p);
END IF;
END LOOP;
--出栈
l_pop_boolean := p_stack.pop(l_value);
l_visited(p_start_object_id) := 0;
END find_all_path;
END cux_util_pub;
?测试脚本
DECLARE
p_status_code VARCHAR2(240);
p_msg VARCHAR2(240);
p_stacks_tbl cux_util_pub.stacks_tbl;
BEGIN
cux_util_pub.find_dependencies(p_start_name => 'CUX_TEST_D'
,p_start_type => 'PACKAGE'
,p_start_owner => 'APPS'
,p_end_name => 'CUX_TEST_A'
,p_end_type => 'PACKAGE'
,p_end_owner => 'APPS'
,p_status_code => p_status_code
,p_msg => p_msg
,p_stacks_tbl=>p_stacks_tbl);
dbms_output.put_line(p_status_code);
dbms_output.put_line(p_msg);
END;结果如下
?上图的p_stacks_tbl变量，存储了所有路径的栈，将栈里的元素一个个弹出，就是正确的A-B-C-D顺序
该算法无法处理有向带环图，比如下面的例子
后期进行优化