玻尔百科大型软件的复杂性堪比一座繁华的都市，无数函数以通常难以追踪的方式相互作用。如果没有地图，要想在这片复杂中穿行，进行调试、优化或仅仅是理解系统，都是一项艰巨的挑战。这正是调用图——一个源自计算机科学的强大概念——所优雅解决的根本问题。它提供了一幅程序“对话”的可视化蓝图，使得不可见的执行流变得可见且可分析。
本文将探讨调用图的理论与实践。在第一部分 原理与机制 中，我们将深入探讨什么是调用图，区分可能性的静态地图和单次执行的动态旅程。我们还将审视这些图是如何构建的，以及分析它们的理论基础。随后，应用与跨学科联系 部分将展示这个抽象模型如何成为软件开发者、架构师和安全分析师不可或缺的工具，使他们能够追查错误、设计稳健的系统、调整性能并保护关键应用。
想象一下，你正在查看一座庞大繁华都市的建筑蓝图。建筑物是重要的地点，而道路连接着它们，展示了你如何从一个地方去到另一个地方。一个计算机程序，特别是大型程序，与这座城市非常相似。它的函数或方法就是建筑物——完成工作的地方。而这些函数之间的“对话”，即一个函数调用另一个函数来协助自己，就是道路。
调用图（call graph）正是这样一幅蓝图。这是一个简单却极为强大的思想，源于一个名为图论的数学领域。我们将程序表示为一个有向图 。顶点（vertices）集合 就是我们程序中的所有函数。边（edges）集合 代表调用关系。如果函数 u 调用了函数 v，我们就画一条从 u 到 v 的有向边——一个箭头。
让我们具体说明一下。考虑一个包含 main、fetch_data、process_batch 和 log_error 等函数的小程序。如果 main 调用了 fetch_data，我们就画一个箭头：main fetch_data。如果 fetch_data 调用了 process_batch，我们再加一个箭头：fetch_data process_batch。如果一个函数是递归的，即它会调用自己，该怎么办？我们只需画一个指回同一顶点的箭头，形成一个自环（self-loop）。
这张简单的地图已经能告诉我们很多信息。我们可以看一个函数，计算指向它的箭头数量——即它的入度（in-degree）。这告诉我们有多少其他函数依赖它，是其职责或重要性的一个度量。像 log_error 这样的函数可能有很高的入度，因为程序的许多不同部分都可能需要报告错误。我们也可以计算从一个函数出发的箭头数量——即它的出度（out-degree）。这反映了它自身的复杂性；一个高出度的函数就像一个管理者，将许多任务委托给其他函数。整个程序的交互结构在这张优雅的图表中一览无余。
这里我们遇到了计算机科学中一个最美妙也最关键的区别：可能发生什么与实际发生什么之间的差异。我们刚才描述的调用图是静态调用图（static call graph）。它是完整的路线图，展示了程序执行可能采取的每一条路径。它是关于源代码本身的一个永恒真理。
但是当你实际运行程序时会发生什么呢？你不会同时走遍所有的路。你只会沿着一条单一的路径，完成一次穿越城市的旅程。这次特定旅程的记录就是动态调用图（dynamic call graph），或者更准确地说，是动态激活图（dynamic activation graph）。在某次特定执行中，每当一个函数被调用，它就创建了一个全新的、唯一的“激活实例”。这个动态图按照它们发生的顺序将这些激活实例连接起来。
为了看清这种显著差异，考虑最极端的情况：一个函数 f 递归调用自己，且没有停止的途径——一个完美的无限循环。
f，带有一个自环。它表示：“函数 f 有可能调用 f。”仅此而已。f 的第一次调用（我们称之为激活 ）再次调用 f，创建了激活 。 创建了 ，如此无限进行下去。这个动态图是一条无限的、无环的链：。静态地图展示了一个带有环岛的地点，而实际的旅程却是一条通往虚无的无限高速公路！这揭示了所有可能性的静态世界与单一、展开的现实动态世界之间的深刻差异。静态图对于理解程序的结构至关重要，但动态轨迹讲述的是在特定的一天、使用特定的输入时所发生的故事。
如果静态调用图是如此基础的蓝图，那么编译器究竟是如何构建它的呢？这不是魔法；这是一个分阶段进行的、充满逻辑的过程。
首先，许多语言（如 C 语言）有一个预处理（preprocessing）阶段。这是一个纯文本操作，类似于查找和替换，在“真正”的编译开始之前运行。如果你的代码中有宏，预处理器会展开它们。如果代码中有像 #ifdef DEBUG 这样的条件编译块，它会根据配置包含或丢弃那段文本。编译器甚至永远看不到宏或被丢弃的代码；它只看到最终的词法单元流。因此，调用图是基于这段预处理后的代码构建的。宏内部的调用会变成使用该宏的函数的真实调用，而被禁用的 #ifdef 块内的调用则会消失，不会为图贡献任何边。
预处理之后，编译器会解析代码。在解析过程中，它可以执行一种语法导向翻译（syntax-directed translation）来构建图。想象一下编译器正在读取一个函数定义。它会记录当前所在的函数——我们称之为 current_caller。每当遇到一个函数调用表达式时，它就知道被调用函数的名称——即 callee。在那一刻，它执行一个简单的操作：将一条边 current_caller callee 添加到它正在构建的图中。通过对整个程序系统地执行此操作，它逐条边地构建出完整的静态调用图。
一旦我们有了地图，我们就可以提出问题。也许最基本的问题是可达性（reachability）问题：从函数 s 开始，我们程序的执行能否通过任何调用序列，最终到达函数 t？。这个问题至关重要，应用范围从错误追踪（在 s 处的错误输入是否会影响到敏感函数 t？）到优化（如果 t 永远无法从主程序到达，也许它是可以移除的死代码？）。
在图论中，这是经典的“有向 s-t 可达性”问题。有趣的是，这个实用的软件工程问题也是计算复杂性理论（computational complexity theory）的基石之一。高效地解决这个问题是一个深刻而优美的挑战。最精确地描述这个问题的复杂性类别是 NL，即“非确定性对数空间”（Nondeterministic Logarithmic Space）。
不要被这个名字吓倒。它的直觉非常美妙。想象你有一个“完美的猜测者”在探索调用图。为了找到从 s 到 t 的路径，它从 s 开始，在每个函数处，它非确定性地猜测下一个要访问的函数。为确保它不会永远徘徊，它只需要少量内存：一个位置来记住当前所在的函数，另一个位置来计算步数（如果路径长度超过函数总数就停止）。所需的内存量非常小——与函数数量的对数成正比，而不是函数数量本身。这种令人惊讶的联系揭示了程序分析的实践艺术与计算的抽象科学之间深刻的统一性。
到目前为止，我们的世界一直很整洁。但现实世界的代码是混乱的。如果你在 C 语言中有一个函数指针（function pointer），或者在 C# 中有一个 delegate 怎么办？在编译时，编译器可能无法确切知道将调用哪个函数。它可能只知道该指针可能指向三个函数中的一个。
为了创建一张有用的地图，编译器必须保守（conservative）。它必须遵循稳健性（soundness）原则，这意味着静态调用图必须是现实的过近似（over-approximation）。它必须包含运行时可能发生的每一次调用。为了实现这一点，如果一个函数指针可能调用 g、h 或 i，编译器必须从调用函数添加三条边——一条到 g，一条到 h，一条到 i。
这保证了图是稳健的——没有可能的运行时调用被遗漏——但这是以牺牲精确性（precision）为代价的。分析可能包含在任何实际执行中从未发生的边。这些是误报（false positives）。例如，静态分析可能确定函数 f 可以调用 j，但由于程序的逻辑，这种情况永远不会发生。边 f j 就是一个误报——地图上的一条从未有车走过的路。这种在稳健性与精确性之间的权衡是程序分析科学中的一个核心主题。
构建正确且精确的调用图是一个活跃的研究领域，不断受到新编程范式的推动。
面向对象编程：在像 Java 或 C++ 这样的语言中，当你看到像 shape.draw() 这样的调用时，实际运行的方法取决于 shape 对象的运行时类型。它是一个 Circle、一个 Square，还是一个 Triangle？这就是虚分派（virtual dispatch）。一个简单的分析可能会添加指向整个程序中所有 draw 方法的边，这虽然是稳健的，但非常不精确。更智能的分析会尝试裁剪这些边。它们执行指针分析（points-to analysis）来确定 shape 对象可能类型的一个更小的集合。它们甚至可以利用控制流信息；例如，如果一个 shape.draw() 调用发生在一个 if (shape instanceof Circle) 块内，分析就知道它只可能是 Circle.draw()，从而裁剪掉所有其他边。
反射：这是最棘手的挑战之一。在这里，程序可以在运行时将一个方法名构造成字符串，然后调用它。调用 invoke("my" + "Method") 对简单的分析来说是不透明的。为了处理这个问题，分析器还必须成为一个字符串分析（string analysis）专家，试图预测所有可能生成的字符串。这也迫使分析器面临开放世界问题（open-world problem）：如果字符串命名了一个将在稍后从网络动态加载的类中的方法怎么办？为了保持稳健性，分析必须要么假设一个封闭世界（closed world，即没有新代码被加载），要么添加一条摘要边到一个特殊的“未知代码”节点，以承认它无法知晓之事。
动态分析的陷阱：鉴于静态分析的复杂性，为什么不直接运行程序并记录所有发生的调用呢？这就是动态分析（dynamic analysis）。对于你观察到的执行，它是完全精确的。然而，它可能会遭受漏报（false negatives）——它可能错过那些可能发生但在你的测试运行中恰好没有发生的调用。错过一个只在罕见错误条件下发生的调用的概率可能很高。如果一个调用在一次完整运行中发生 5 次，而你的采样分析器的采样率为 ，那么至少一次观察到它的机会很高，但完全错过它的机会是一个非零值 。对于那些罕见但至关重要的行为，单独依赖动态分析可能是一场危险的赌博。
最后，至关重要的是要将调用图与一个相关但不同的概念区分开：调用栈（call stack）。调用图是关系的静态地图。调用栈是一个动态的、运行时的数据结构，用于跟踪活动的函数调用。它以后进先出（Last-In, First-Out, LIFO）的方式运作。当 f 调用 g 时，g 的激活记录被推到 f 的记录之上。当 g 返回时，它的记录被弹出。
调用栈的深度告诉你任何给定时刻有多少层嵌套调用是活动的。这个深度是执行的一个动态属性，它不一定对应于静态调用图中路径的长度。
考虑以下两种情况：
F() G() H()。静态图中最长简单路径的长度为 3（F, G, H）。运行时的最大栈深度也是 3。它们匹配。T(10)。静态图是一个带有自环的单节点。最长的简单路径长度为 1（节点本身！）。但在执行期间，随着 T(10) 调用 T(9)，T(9) 调用 T(8)，以此类推，调用栈的深度将增长到 11。静态图的结构和动态栈的行为是程序生命中两个不同但相关的方面。图展示了可能性的网络，而栈衡量了单次穿越该网络的瞬时资源使用情况。理解两者是理解程序真正如何工作的关键。
地图并非领土本身，但它是对领土极其强大的抽象。它让我们能够看到关系、规划旅程，并识别出那些我们否则会错过的重地。调用图就是我们软件领土的地图。我们已经看到了如何绘制这张地图，用节点和箭头代表函数及其调用。现在，我们将踏上一段旅程，去看看它揭示了什么。我们会发现，这个简单而优雅的思想不仅仅是一个描述性工具，它是一个强大的分析透镜，让我们能够以一种前所未有的清晰度来调试、优化、架构和保护我们的软件。我们即将看到这个抽象的图如何成为软件侦探、架构师和安全卫士的实用指南。
在最基础的层面上，调用图使程序的无形流动变得可见。对于一个试图理解复杂代码库或追踪错误的程序员来说，这是一份无价的礼物。
想象一下最可怕的简单错误：一个程序无休止地调用自己，耗尽所有内存并崩溃。这被称为无限递归。在调用图上，这并不那么神秘；它只是一个环。一个调用自己的函数会创建一个小环，即一条自环边。一个函数 调用 ，而 又反过来调用 ，则会形成一个更大的环。通过将调用图视为一个简单的连接网络并搜索环路，我们可以为潜在的无限递归获得响亮的警报。这是一个非常简单且保守的检查：并非每个环都会导致错误，但每个无限递归必定存在于一个环内，这为程序员提供了开始调查的精确位置。
现在，假设一个程序在一个特定的“错误函数”处崩溃。问题总是，“我们是怎么到这里的？”调用图提供了路线图。从一个已知的起点找到通往错误状态的最短调用序列，等同于在图中寻找最短路径——这是一个经典问题，可以通过广度优先搜索（BFS）或迭代加深深度优先搜索（IDDFS）等算法解决。这项技术对于调试复杂系统非常有价值。在安全领域，这通常是理解攻击者如何穿过代码到达易受攻击的函数并触发漏洞利用的第一步[@problem_-id:3227691]。
除了发现单个错误，调用图还揭示了软件系统的宏伟架构。它的形状可以告诉我们一个程序是组织良好的城市，还是一团乱麻。
软件总是在不断变化。如果你修改了一个底层的工具函数，系统的哪些其他部分可能会受到影响？没有地图就回答这个问题是一场猜测的噩梦。有了调用图，这就是一次系统性的搜索。我们想要找到所有可能直接或间接调用我们修改过的函数的函数。这正是寻找图的传递闭包（transitive closure）的问题。通过计算它，例如使用 Floyd-Warshall 算法，我们可以生成一份完整的“影响报告”，确保变更的任何意外副作用都不会被忽视。
一个设计良好的系统有清晰的边界和明确定义的职责。而一个设计糟糕的系统通常会表现出“代码异味”，调用图的结构本身就能让它们显现出来。
想象一座桥，它是从一个岛屿到另一个岛屿的唯一途径。如果它倒塌了，岛屿之间的联系就断了。在一个划分为模块（我们的“岛屿”）的软件系统中，一些函数调用扮演着这样的桥梁角色。调用图中作为桥（bridge）并连接两个不同模块的边，代表了一个关键的、单点故障。移除这个单一的调用关系就会分割组件的连通性。识别这些“桥调用”能让软件架构师发现并加固这些模块间脆弱且通常不受欢迎的紧密耦合。
此外，网络科学中的概念可以应用于调用图，以发现其他类型的架构弱点。在任何网络中，一些节点比其他节点更重要。一些节点有大量的入连接（高入度），使其成为“枢纽”。另一些节点位于大量其他节点间的最短路径上（高介数中心性），使其成为“瓶颈”。当这些特性出现在调用图中时，它们通常对应于“上帝函数”或过于复杂的控制器——那些做得太多、知道得太多的函数。通过应用统计方法，即使在考虑了函数大小等混淆因素后，识别出那些中心性病态高的函数，我们也能以数据驱动的方式精确定位架构弱点，指导重构工作并改善软件设计。
调用图不仅决定了逻辑流程，还决定了程序消耗的物理资源——时间和内存。
一个递归函数每次调用都会消耗栈内存。它到底需要多少内存呢？通过将递归调用建模为穿越调用图的一条路径，其中每一步都减小了问题的规模，我们可以模拟其执行。在达到基本情况之前可能的最长路径给了我们最大的栈深度——这是防止栈溢出错误的一个至关重要的指标，尤其是在像嵌入式系统这样的内存受限环境中。如果我们发现一条路径可以在不减小问题规模的情况下形成循环，我们就发现了一条通往无限栈增长和程序不终止的路径。
现代操作系统只在需要时才从磁盘加载代码，这个特性被称为“按需分页”（on-demand paging）。每次一个函数首次被调用时，都可能触发一次“缺页中断”（page fault）以将其代码加载到内存中。通过按执行顺序遍历调用图，我们可以精确计算访问了多少个新函数（以及因此产生的新页面）。对于一个调用形成规则树状结构的程序，我们甚至可以根据树的深度和分支因子推导出一个优美的封闭形式表达式来计算总的缺页中断次数。
要让程序更快，你必须首先找出是什么让它变慢。如果我们在调用图的边上加上权重，其中每个权重是调用的执行时间，那么这个图就从一个简单的流程图转变为一张延迟（latency）图。性能的“关键路径”（critical path）就是这个加权图中的最长路径。对于有向无环图（DAG）——在处理完递归后，这在性能分析中很常见——这条路径可以使用基于拓扑排序的算法高效地找到。这精确地指出了对总延迟贡献最大的调用链，告诉工程师们应该将优化精力集中在哪里。
编译器自身也使用调用图来执行复杂的优化，而这种分析的精确性至关重要。例如，“尾调用”（tail call）是一种特殊的函数调用，调用者在调用后立即结束。一个简单的调用图模型会增加一层新的深度，可能会混淆分析。然而，一个更智能的模型会认识到尾调用更像一个 goto 语句。通过将其建模为一个保留调用上下文的过程序内跳转，编译器可以保持关于数据流的更精确信息，从而带来更好的优化，如常量传播。
在区块链和智能合约的世界里，一个错误不仅仅是不便——它可能导致数百万美元的不可逆损失。在这里，调用图不仅仅是良好设计的工具；它是一道关键的防线。
最臭名昭著的智能合约漏洞之一是“重入攻击”（reentrancy attack）。当一个恶意合约在与受害者合约进行交易的过程中，在初始交易完成之前回调受害者合约时，就会发生这种攻击。这种重入可能让攻击者通过利用不一致的状态来耗尽资金。在一个投射到合约层面的调用图上，这个漏洞表现为一个环。从合约 到 的调用，随后是从 回调 的调用，就形成了一个重入环。通过系统地构建调用图，包括解析动态调用和建模不同调用类型的特殊行为，安全审计员可以在这些潜在的灾难性漏洞被部署之前自动检测并标记它们。
因此，调用图远不止是一张图表。它是连接我们代码的静态文本和其执行的动态现实之间的桥梁。它提供了一种通用的语言和一个统一的框架，用来提出——并回答——范围广泛的问题。无论我们是在追踪一个错误、重新设计一个系统、为性能调优，还是在寻找一个安全漏洞，旅程往往都始于绘制这张地图，并看看它揭示了什么。调用图的内在美在于其非凡的转化力量：将复杂的代码网络变成一个简单、优雅的结构，其属性告诉我们如此之多关于我们所构建的世界的信息。