构建基于 CDT 的编辑器，第 4 部分: 高级 CDT 解析和持久文档对象模型

核心提示：为什么要学习另一个解析器呢？外部链接是使 C/C++ 中的代码分析变得困难的原因之一，不管在哪里声明一个变量或函数，构建基于 CDT 的编辑器，第 4 部分: 高级 CDT 解析和持久文档对象模型，extern 关键字都允许其他文件在不确定其定义位置的情况下使用该文件，当要显示它们的相互依赖关系时，在第 5 部分中，我

为什么要学习另一个解析器呢？

外部链接是使 C/C++ 中的代码分析变得困难的原因之一。不管在哪里声明一个变量或函数，extern 关键字都允许其他文件在不确定其定义位置的情况下使用该文件。当要显示它们的相互依赖关系时，Eclipse 的 Outline 视图（在图 1 左侧显示）却起不到什么作用。该视图只显示单个源文件的元素。在右侧，Index 视图却显示全部 CDT 项目全部文件的每个元素。如果正要构造复杂的、内部相互联系的项目，第二种方式是至关重要的。

图 1. Outline 视图 和 Index 视图

可以使用在 第 3 部分 中描述过的解析器来构建 Index 视图，但一旦任何代码进行了修改，该视图就不得不解析 CDT 工作空间中的每个源文件。那是不切实际的。

为使诸如 Index 视图这样的功能可用，CDT 开发人员创建了一个新的解析过程，该解析过程将其结果存储于内存映射文件中。这种持久性使解析器能够只分析最近更改的文件就能访问项目中存储的元素。除提供 Index 视图外，这个改进了的解析过程也使一些功能如代码完成及内容协助成为可能。

PDOM 解析器如何工作

新的解析过程跟第 3 部分中的讨论是有联系的。新的解析器和旧的 Parser 实质上的功能实现是一样的。它们包含相似的方法并创建相似的抽象语法树（AST）。但新过程有许多更改。我将其操作概括为四个步骤：

启动索引器任务

解析 TranslationUnit

更新 PDOM

PDOM 结构和存储

为了能够看到这些概念在代码中是如何实现的，我更新了精简版 C/C++ 开发工具（BBCDT）来创建项目元素的索引并显示特定的节点类型。为激活它，我更新了之前的 ASTAction 来访问 AST 以及 PDOM 存储中的元素（代码请参见 下载）。

步骤 1：启动索引器任务

当启动核心插件时，它会创建一个 PDOMManager 来监控新的解析过程及其持久性。该管理程序本身并未完成什么，但它会在新 CDT 元素（特别是 CProject 和 TranslationUnit）出现在工作空间中时做出响应。当创建了新的 CProject时，PDOMManager 会创建一个索引器来寻找并存储该项目源文件中的元素。

该索引器实现 IPDOMIndexer，但其类依赖于用户的 CDT 首选项。图 2 显示三项索引选项，其中默认选择了 No Indexer 。当选择 No Indexer 时，PDOMManager 会创建一个什么也不做的 NullPDOMIndexer。如果选择 Fast C/C++ Indexer 选项，PDOMManager 会创建一个 FastPDOMIndexer，如果选择 Full C/C++ Indexer 选项，PDOMManager 会创建一个 FullPDOMIndexer。创建了索引器后，管理程序就会让索引器开始构建索引。

图 2. Indexer 首选项

索引的目标是记录项目源代码中所有已命名的元素并将它们与其相关数据一起存储。这是一个复杂的过程，且能在后台运行，所以它被作为一个 Eclipse Job 执行。特别地，该索引器创建了一个带 Job.LONG 优先级的索引 Job，并将其添加到平台的队列中。

如果刚创建了该项目，Job 并没有多大功能，因为还没有可以索引的代码。然而，它的确为项目构建了一个非常重要的叫做 PDOM 的对象。它提供了将索引器的数据存储到 PDOM 的例程。

变化的 PDOM
我在 2006 年 10 月撰写这篇文章时，PDOM 及其解析过程尚未 最终定案。事实上，许多对 CDT 新闻组困惑的响应者都甚至会告诉你，它不稳定。但它代表着 CDT 代码分析的未来，即使其细节会改变，先理解一下其概念也是很重要的。它在启动 CDT 功能（内容协助、代码完成、索引等等）方面起到了重要的作用，且这种作用会随着继续开发而得到加强。

不同于第 3 部分中的 Parser，索引器不会立即启动或自动启动。相反，PDOMManager 等待着对 CProject 的更改，如一个新的、修改过的或删除的源文件。当它检测到一个更改时，它会让索引器开始分析，与此同时，索引 Job 认真地开始工作。特别是，它寻找更改过的 TranslationUnit 和代表了该单元源代码语言的 ILanguage。然后通过调用 ILanguage.getASTTranslationUnit() 启动解析过程。

步骤 2：解析 TranslationUnit

第 3 部分中的 Parser 并未在编程语言上进行区分。它寻找 C 和 C++ 元素并使用它们来创建一个通用 AST。新过程以不同的方式工作。每个 TranslationUnit 中都有一个 ILanguage 对象，该对象指定如何解析该单元。如果要为 CDT 添加一门定制语言，要从创建自己的 ILanguage 开始。值得感激的是，CDT 默认提供了两种语言：GCCLanguage 和 GPPLanguage。

类似地，CDT 提供两种默认的解析器用来实现 ISourceCodeParser：GNUCSourceParser 和 GNUCPPSourceParser。解析过程本身和在第 3 部分中描述的相同。代码阅读器从源文件中创建一个字符缓冲，扫描器将字符组合到 IToken 中，解析器将 IToken 组合成 IASTNode。甚至连方法名（translationUnit()、declaration()、statement() 等）也是一样的。下列是新旧解析过程的主要区别：

新解析器是特定于语言的 —— 节点扩展了 CASTNode 或 CPPASTNode。

新解析器通常在 COMPLETE_PARSE 模式下运行，所以它们通常在函数中进行解析。

新解析器在一个 ILocationResolver 中存储额外的解析信息（问题、节点位置），而不是存储在回调对象中。

新解析器只在元素被请求时确定元素的范围。

新 AST 的顶端节点是一个 IASTTranslationUnit，其结构能被 ASTVisitor 遍历。

请记住：旧的 Parser 返回一个 IASTCompilationUnit。PDOM 解析器返回 IASTTranslationUnit ，或更明确地说，是CASTTranslationUnit 和 CPPASTTranslationUnit。

上述第四个区别很重要。解析器不能确定元素是如何使用的，除非它知道元素的范围。旧的 Parser 在用 translationUnit() 启动解析时创建一个顶层的范围。然后它将这个范围传递给进一步的方法，如 declaration()，该方法创建并在必要时传递子范围。当旧的 Parser 运行完成时，它就有了其 AST 中每个元素的范围。新解析器创建单个范围且在操作过程中不会改变。这是因为索引器只对特定的节点集感兴趣。为解释这个以及其他有趣的特性，我需要描述一下索引器使用解析器的 AST 将如何工作以及它如何同 PDOM 进行交互。

步骤 3：更新 PDOM

索引器接收到 IASTTranslationUnit 后，会得到在 PDOM 上的一个写锁并开始保持 TranslationUnit 的数据。首先，它调用 IASTTranslationUnit.getIncludeDirectives() 和 IASTTranslationUnit.getMacroDefinitions()。然后，它存储一个对 PDOM 中的单元文件的引用以及对所包含的指令和宏定义的其他引用。这些引用以 PDOMFile 的形式（可以通过 PDOM.addFile() 来存储）存在。

为搜索或访问 AST，索引器创建一个新的 ASTVisitor 并调用 IASTTranslationUnit.accept(ASTVisitor)。AST 中的每个IASTNode 都有一个 accept() 方法，每个方法都以近乎相同的方式运行：

检查 ASTVisitor 的 Boolean 字段中的一个，来确定访问器是否对访问此节点感兴趣。

如果感兴趣，该节点调用访问程序的 visit() 方法，该方法返回下列三个值中的一个：

PROCESS_SKIP —— 访问程序对该节点的子节点不感兴趣，所以 accept() 返回 true。

PROCESS_ABORT —— 访问程序对访问根本不感兴趣，所以 accept() 返回 false。

PROCESS_CONTINUE —— 访问程序要访问该节点的子节点，所以 accept() 继续到下一步。

如果 Boolean 字段为 false 或 visit() 返回 PROCESS_CONTINUE，accept() 调用每个子节点的 accept() 方法并将访问程序当作其参数。

例如，如果一个 C 函数声明有一个声明修饰符，如 typedef 或 static，其相应的 CASTFunctionDefinition.accept() 方法检查访问程序的 shouldVisitDeclarations 字段。如果该字段为 true，它会调用访问程序的 visit()方法。如果该字段为 false 或 visit() 返回 PROCESS_CONTINUE，该函数节点访问其子节点并调用 CASTSimpleDeclSpecifier.accept()。当访问程序到达其中一个最后的（或终端）节点，accept() 只返回 ture。

表 1 显示了 Boolean 字段，该字段控制哪种类型的节点能够调用访问程序的 visit() 方法。默认情况下，它们都被设为 false，所以永远都不会调用 visit()。

表 1. 控制节点访问的 ASTVisitor 字段

shouldVisitNames	shouldVisitDeclarations	shouldVisitInitializers
shouldVisitDeclarators	shouldVisitDeclSpecifiers	shouldVisitExpressions
shouldVisitTypeIds	shouldVisitEnumerators	shouldVisitTranslationUnit
shouldVisitParameterDeclarations	shouldVisitStatements	shouldVisitProblems

理解 ASTVisitor 如何工作的最佳方法是来看一个例子。清单 1 显示了由 PDOMFullIndexerJob 使用的用来寻找 IASTName 节点的访问程序。为访问这些节点，它将 shouldVisitNames 和 shouldVisitDeclarations 设置为 true。

清单 1. PDOMFullIndexerJob 的 ASTVisitor

ast.accept(new　ASTVisitor()　{　
　　//　Set　the　Boolean　fields　so　that　name　and　declaration　nodes　call　visit()　
　　{　
　　　shouldVisitNames　=　true;　
　　　shouldVisitDeclarations　=　true;　
　　}　
　
　　//　Perform　the　visit　
　　public　int　visit(IASTName　name)　{　
　　　try　{　
　　　　　IASTFileLocation　fileloc　=　name.getFileLocation();　
　　　　　if　(fileloc　!=　null)　{　
　　　　　　PDOMFile　file　=　pdom.addFile(fileloc.getFileName());　
　　　　　　linkage.addName(name,　file);　
　　　　　}　
　　　　　return　PROCESS_CONTINUE;　
　　　}　catch　(Throwable　e)　{　
　　　　　CCorePlugin.log(e);　
　　　　　return　++errorCount　>　MAX_ERRORS　?　PROCESS_ABORT　:　PROCESS_CONTINUE;　
　　　}　
　　};　
});　

如图所示，索引器的访问程序只对 IASTName（存储于 PDOM 中惟一的一些的节点）感兴趣。这些节点代表了具体的标识符，如函数名称、变量及枚举类型。当访问程序到达其中一个节点时，它会访问表示了该名称的源文件的 PDOMFile 对象。然后使用 PDOM 的链接对象（PDOMLinkage）来将 IASTName 添加到索引中。

在 IASTName 被存储前，该链接需要知道其类型，或绑定 。例如，是否是变量名、函数名，等等。为找出该类型，该链接寻找节点的父节点及其范围。有了这个范围，该链接可以确定出该名称是如何使用的，并将该信息封装至一个 IBinding 中。这就是为什么新解析过程要在解析后作出范围确定的原因 —— 它只对 IASTName 的范围感兴趣。

为澄清名称及绑定，我调试了 CDT 对 Hello World 程序的解析并在图 3 中提供了 AST 的分解。AST 包含了代表 main() 函数的单个的 IASTDeclarationUnit。CASTFunctionDeclarator 持有一个 CASTName，其 IBinding 为 CFunction。

图 3. Hello World AST

该链接将 IBinding 修改为一个持久的 PDOMBinding，并将 IASTName 修改为一个 PDOMName。这些新对象的构造函数访问 PDOM 以存储其信息。为显示其工作原理，我需要备份并解释 PDOM 是如何操作的。

步骤 4：PDOM 结构

如果您已经创建过 CDT 项目，我推荐您打开工作空间目录及其下面的 .metadata/plugins/org.eclipse.cdt.core 目录。在那里，将看到每一个项目的一个 *.pdom 文件。为项目创建了一个 PDOM 后，它会构造一个 Database 对象来管理其底层存储。Database 构建一个新 RandomAccessFile 并将项目名称和时间（以毫秒为单位）赋给它 —— 这就是所看到的 *.pdom 文件。

Java I/O 和 Java NIO

我见过的大多数 Java™ 输入/输出程序都使用 Java I/O 应用编程接口（API）。它以字节流 的方式移动数据，同时提供了 InputStream、OutputStream、Writer 和 Reader。当性能不成问题时，这很好。Java New I/O (NIO) API 中的类会使用类似于操作系统中的那种高效的块传输方法。这对小文件不是很重要，但当文件大小接近操作系统页面的大小（例如，2 KB、4 KB、8 KB）时却大有区别。很不巧，Database 将其 *.pdom 文件初始化为 16 KB。

在 CDT 中，最重要的 Java NIO Buffer 是 MappedByteBuffer，它创建在现有 RandomAccessFile 的顶部。一般文件访问需要缓冲、堆分配以及文件 I/O 程序。而，MappedByteBuffer 会被虚拟内存控制器立即更新，且内存并不影响 Java 堆。既然 MappedByteBuffer 不依赖程序内存，多个程序就能够同时有效地访问它们。但是，由于它在离操作系统极近的地方操作，其行为比 Java I/O 例程更依赖于操作系统。

这个 Database 与常规数据库有着很多的相似之处，这不仅仅体现在名称上。它将内存划分为由一些 16 字节块组成的变长的记录。每条记录代表一个不同的 PDOMNode，如 PDOMLinkage 或 PDOMBinding。为允许内存访问，它为 int、char 和 byte 提供了 put 和 set 方法。

为使读写文件尽量高效，Database 使用一组 Chunk 在 *.pdom 文件上管理 MappedByteBuffer。当 Database 创建这个文件时，它将其大小设为 16 KB，并分配数组中的第一个 Chunk 来进行缓冲。当索引需要更多的内存，Database 会创建另一个 16 KB 的 Chunk。

添加到数据库中的第一个对象是 PDOMLinkage。当项目中使用新语言时，也会添加新链接。当调用其构造函数时，PDOMLinkage 会：

将其初始记录大小设置为 24 字节。

存储 0 来代表节点的类型（链接）。

存储 0 以表示其不含父节点。

存储用来存储链接名称所需内存的大小。

分配内存并存储链接名称。

存储用来存储链接 ID 所需内存的大小。

分配内存并存储该链接的 ID。

如果这是第一个项目链接，将其记录大小存储到一个特定的地址。如果不是第一个项目链接，它会寻找下一个可用地址并将该大小存储到那里。

内存分配由 Database.malloc(int size) 执行，它首先确定用于提供所请求内存的块的最小数目。如果没有足够的可用内存，它会创建一个新的 Chunk。否则，它访问能够提供内存的 Chunk，清空块的请求数目，并返回第一个被分配的块的位置。

其他对象的存储过程也是一样，例如链接会创建一个新的 PDOMBinding 作为存储已命名节点的一部分的情况。如果该绑定未包含在另一个绑定的范围内，该链接将其自身设置为该绑定的父绑定。然后，PDOMBinding 构造函数将其初始记录的大小设为 24 字节并执行和上述所列各步骤大致相同的步骤。

PDOMName 以不同的方式工作。有三种方式将名称与其绑定联合在一起：定义、声明或引用。当 PDOMName 确定了其角色后，它会更新 PDOMBinding 的记录。然后存储包含该 PDOMName 的 PDOMFile（其文件中还包含 PDOMName 的位置和长度）的位置。最终，它通过将其块位置添加到 PDOMFile 来填充该文件的索引。

由于多个 PDOMNode 间的父/子关系，该索引构造了一棵和解析器的 AST 类似的树。第一次调用 PDOMLinkage.getIndex() 时，它会使用 PDOM 的 Database 和根块位置来创建一棵 BTree。可以用一个 IPDOMVisitor 仔细搜索这棵树。这和 ASTVisitor 的运行相似，但有三点重要区别：

它不含 Boolean 字段 —— 所有的节点都访问到了。

它只使用单个的 visit(IPDOMNode node) 方法，该方法检查访问到的节点是否属于某一个类型。

它包含一个 leave(IPDOMNode node) 来在到达一个特定的节点类型时停止搜索。

也可以使用在 DOMSearchUtil 类中提供的静态方法来搜索 PDOM。

更新 BBCDT

我已经添加了 PDOM 类，考虑到该应用程序的大小，精简版似乎不再合适。我设置了PDOMManager 来为项目索引创建仅有的 PDOMFullIndexer，所以这里不再涉及首选项和描述符。同样，我修改了 ASTAction 以执行两项任务：用 BBASTVisitor 搜索 IASTTranslationUnit，用 BBPDOMVisitor 搜索 PDOM。这些类在 org.dworks.bbcdt.ui.action 包中。单击 ASTAction 的结果如图 4 所示。

图 4. BBCDT 索引的内容

查看原图（大图）

BBASTVisitor 搜索 AST 来寻找 IASTName 和 IASTForStatement。当它发现一个循环时，会显示三种表达式：初始程序、条件及迭代。BBPDOMVisitor 在 BBPDOMVisitor 中寻找函数，并显示当前的数目。

结束语

相对解析、Java NIO 以及伪数据库访问来说，毫无疑问，索引是一个复杂的过程。然而，要提供有效的、包括一切的代码分析及存储，就非常需要这种复杂性。

至此，我已经充分解释了 PDOM，接下来要介绍的是 CDT 该如何应用它。在第 5 部分中，我将探讨代码完成及内容协助，包括二者如何工作以及如何访问 PDOM 索引。

本文源代码下载地址: http://flashview.ddvip.com/2009_12/os-ecl-cdt4.zip