我不能确切地说出任何特定实现使用了哪些算法,但我可以做出一些有根据的猜测。对于这个问题, trie是一种非常有用的数据结构:IDE 可以在内存中维护项目中所有符号的大型 trie,每个节点都有一些额外的元数据。
当您键入一个字符时,它会沿着树中的路径走。特定 trie 节点的所有后代都是可能的完成。然后,IDE 只需要通过在当前上下文中有意义的那些过滤掉那些,但它只需要计算尽可能多的可以在选项卡完成弹出窗口中显示的内容。
更高级的 tab-completion 需要更复杂的 trie。例如,Visual Assist X有一个功能,您只需键入 CamelCase 符号的大写字母——例如,如果您键入 SFN,它会SomeFunctionName
在其制表符补全窗口中显示该符号。
计算 trie(或其他数据结构)确实需要解析所有代码以获取项目中所有符号的列表。Visual Studio 将其存储在其 IntelliSense 数据库中,这是一个.ncb
与项目一起存储的文件,因此它不必在每次关闭和重新打开项目时重新解析所有内容。当你第一次打开一个大项目(比如说,一个你刚刚同步表单源代码控制的项目)时,VS 将花时间解析所有内容并生成数据库。
我不知道它如何处理增量更改。正如您所说,当您编写代码时,90% 的时间它都是无效的语法,并且每当您空闲时重新解析所有内容都会给您的 CPU 带来巨大的负担,而收益却很少,特别是如果您正在修改包含的头文件大量的源文件。
我怀疑它要么(a)仅在您实际构建项目时(或者可能在您关闭/打开它时)重新解析,或者(b)它进行某种本地解析,它仅在您刚刚解析的地方解析代码以某种有限的方式进行编辑,只是为了获取相关符号的名称。由于 C++ 具有如此复杂的语法,如果您使用繁重的模板元编程等,它可能会在黑暗的角落里表现得很奇怪。