本文详细分析了 Github Copilot 这个基于机器学习的代码自动补全工具的实现原理。作者通过逆向工程的方式,深入探索了 Copilot 的核心逻辑,包括代码提示的入口、获取提示的核心方法、以及相关的缓存策略、实验特性等。
本文详细分析了 Github Copilot 这个基于机器学习的代码自动补全工具的实现原理。作者通过逆向工程的方式,深入探索了 Copilot 的核心逻辑,包括代码提示的入口、获取提示的核心方法、以及相关的缓存策略、实验特性等。
众所周知，Github Copilot是一种基于机器学习的代码自动补全工具。它使用了来自GitHub的大量代码作为训练数据，并使用OpenAI的语言模型来生成代码。Copilot还可以学习用户的编码习惯，并根据上下文推断出正确的代码片段。
在实际使用中发现大部份提示还是非常好用的，能够较为准确的推测出用户意图，甚至是基于项目其他文件的上下文进行推理。比较好奇这里是怎么做到的，于是探索了这个VSCode插件的详细实现。
由于Copilot并没有开源，因此我们需要做一些逆向的准备。
首先，找到VSCode插件的安装目录，拿到extension.js：
在mac下插件目录在~/.vscode下，我们可以拿到一个经过压缩混淆的文件：
webpack_modules针对整个webpack压缩混淆的js，我们首先要将不同的bundle识别出来，分割成单个文件，以便于后续的分析。
由于压缩后的代码存在很多不确定性，一开始打算尝试通过正则提取，但无论如何都有各种边界情况导致提取不正确，最简单的方法还是通过AST来提取。
首先，通过babel-parser将源码解析为AST：
const ast = parser.parse(source);然后，通过babel-traverse遍历整个AST，找到modules的变量，取出里面的值：
…最后，将处理过后的ast通过babel-generator和babel-types重新生成新的ast写入文件。
这样，我们就得到了以模块id命名的独立bundle，在我的这一版中，解析出来的copilot的bundle已经非常多了，达到752个。
我们解析出来的bundle，第一层函数大概是这样：
对于webpack来说，这几个参数是固定的，分别是module、exports、require，所以我们优先把这几个参数识别出来，进行作用域的替换，这样才可以看出模块间的依赖关系：
…这样，我们就得到了类似这样的有require和exports的代码：
var r = require(12781).Stream;
var i = require(73837);
function o() {
this.source = null;
this.dataSize = 0;
this.maxDataSize = 1048576;
this.pauseStream = !0;
this._maxDataSizeExceeded = !1;
this._released = !1;
this._bufferedEvents = [];
}
module.exports = o;JS代码经过压缩后，会产生大量的逗号运算符、短路写法、三元表达式、括号闭包等等，非常阻碍阅读，这里参考了https://github.com/thakkarparth007/copilot-explorer 这个项目所做的一些逆向工作，对语法进行了一系列处理：
…由于压缩之后的代码，require依赖只有moduleid，已经失去了原来的文件名称，所以这里我们需要手动映射（当然也可以借助GPT）推断一下不同文件的名称，维护一个map文件，然后在ast里将模块id替换为有语义的模块名：
…至此，我们逆向相关的准备工作就完成了。
虽然前面我们已经为逆向做了大量的工作，但实际上，逆向JS代码还是一个体力活，在有限的精力下，我们也只能手动将一些上下文压缩变量进行推断替换，尽可能还原一些核心文件的代码。
入口可以很轻易找到它的模块id是91238：
经过一系列的手动优化操作，我们可以大致还原这个入口文件的原始样貌：
在VSCode的active函数中，copilot做了大量初始化相关的工作，以及将各个模块的示例注册到context中，后续取实例就从context上下文来取。
我们的核心还是想探索copilot的代码补全能力，入口文件的细节在这里就不展开了。
代码提示逻辑是在registerGhostText中注册的：
在vscode中，主要通过InlineCompletionItemProvider来实现编辑器中的代码补全能力。
整个实现的入口逻辑经过还原后大致如下：
整体还是比较清晰的，它大致做了以下几件事情：
InlineSuggestEnable、或者document不在处理白名单内，或者用户取消了输入，都会提前return，不进行代码提示。getGhostText方法拿到texts，这个大概就是最终会返回给用户的代码提示文本。completionsFromGhostTextResults，拿到最终的completions。这个函数比较简单，主要对文本进行了一些格式化的处理，比如处理Tab空格的问题，以及根据光标当前的位置计算出代码提示应当显示在编辑器中的坐标范围。getGhostText是获取提示代码的核心方法，整体代码较多，我们将其拆分一下：
const prompt = await extractprompt.extractPrompt(ctx, document, position);提取prompt是一个比较复杂的操作，接下来我们单独拆一小节详细分析。
…这里的边界范围主要是三种情况：
在copilot内部做了两层缓存处理，第一层缓存是保存了上一次的prefix和suffix：
function updateGlobalCacheKey(prefix, suffix, promptKey) {
prefixCache = prefix;
suffixCache = suffix;
promptKeyCache = promptKey;
}这里的promptKey是根据prefix和suffix的内容计算得到。在copilot向后台发起请求前，如果判断这次请求的prefix和suffix还是和之前的一样，则会读取缓存的内容：
紧接着，如果上一层的缓存没有命中，copilot还会计算二级缓存，会计算当前的prompt在不在缓存范围内：
在这里，copilot采取的缓存是LRU缓存策略，prompt默认会缓存100条：
exports.completionCache = new s.LRUCacheMap(100);而keyForPrompt函数就是一个对prefix和suffix的hash：
exports.keyForPrompt = function (e) {
return r.SHA256(e.prefix + e.suffix).toString();
};到了真正到向后台发送prompt请求的时候，copilot还是做了两件比较细致的事情：
Debounce时延contexualFilterScore是否达到阈值首先，为了避免频繁向后台发送请求，copilot做了debounce，要知道模型计算是十分消耗算力的，因此在这个场景下，必须要做debounce。copilot的这个debounce也不是一般的，让我们看看它的实现细节：
exports.getDebounceLimit = async function (e, t) {
let n;
if ((await e.get(r.Features).debouncePredict()) && t.measurements.contextualFilterScore) {
const e = t.measurements.contextualFilterScore;
const r = .3475;
const i = 7;
n = 25 + 250 / (1 + Math.pow(e / r, i));
} else n = await e.get(r.Features).debounceMs();
return n > 0 ? n : 75;
};copilot有一个预测开关，如果这个预测开关打开，会根据当前的内容相关性评分预测当前的debounce时延，这个处理就比较高级了。当然在开关没打开的情况下默认值为75ms。
其次就是contexualFilterScore 了，这个值代表的是上下文的评分，copilot会记录之前几次上下文有没有采纳的结果，貌似是通过一个简单的线性回归来预测当前的上下文被采纳的可能性，如果小于一定的阈值，则不会再给用户进行提示，优化用户体验。
当前版本的阈值应该是35%。这个contextualFilterEnable开关默认是打开的。
最后，就是向后台真正发起请求了：
画个图总结一下copilot向后台发起请求之前做的事情：
Extract首层逻辑其实并不复杂，最终返回了prompt对象：
上图中用红框标出的字段来源于配置，其他的字段来自于getPrompt方法的返回，getPrompt是获取prompt的核心逻辑，这块我们接下来单独展开讨论，先来看看配置的问题。
在copilot（VSCode）体系中，有很多配置是对接了微软的AB实验平台的，可以在文件中找到这样的模块：
…这个就是拉取了ab实验的平台，很多特性开关都是通过配置下发，copilot的相关配置也不例外。
这些配置在平台没有指定的时候，都是以它的默认值。
经过我实际抓包，发现我的Copilot插件配置好像没有经过配置平台单独指定，因此整个字段应该取的默认值：
suffixPercent，默认值为15.fimSuffixLengthThreshold，默认值为0maxPromptCompletionTokens，默认值为2048neighboringTabsOption，默认值为eagerneighboringSnippetTypes，默认值为NeighboringSnippetsnumberOfSnippets，默认值为4snippetPercent，默认值为0suffixStartMode，默认值为CursorTrimStarttokenizerName， 默认值为cushman002indentationMinLength，默认值为undefinedindentationMaxLength，默认值为undefinedcursorContextFix，默认值为false这些会作为Prompt的基础配置字段传给getPrompt方法。
在getPrompt逻辑里，首先扩充了一系列配置字段：
languageMarker，默认值为ToppathMarker，默认值为ToplocalImportContext，默认值为DeclarationssnippetPosition，默认值为TopOfTextlineEnding，默认值为ConvertToUnixsuffixMatchThreshold，默认值为0suffixMatchCriteria，默认值为LevenshteincursorSnippetsPickingStrategy，默认值为CursorJaccard在Copilot中，prompt是由多种类型组合而成，可以在PromptElementKind中找到：
BeforeCursor，是光标前的内容AfterCursor，是光标后的内容SimilarFile，与当前文件相似度较高的内容ImportedFile：import依赖LanguageMarkder，文件开头的标记语法PathMarker，文件的路径信息Copilot实现了一个优先级的辅助类，用来设置不同类型的Element优先级：
…可以看到justAbove和justBelow，就是生成一个比传入优先级略高或略低的优先级，保证这个优先级在目前的情况下只比传入的优先级高或低一点。
在Copilot中，不同类型的优先级是这样产生的：
…这里可以简单推断一下：
beforeCursorPriority，为0.5languageMarkerPriority，为0.25pathMarkderPriority，为0.375importedFilePriority，为0.4375lowSnippetPriority，为0.40625highSnippetPriority，为0.75所以在默认的场景下，这几种类型的优先级排序为：highSnippetPriority > beforeCursorPriority > importedFilePriority > lowSnippetPriority > pathMarkderPriority > languageMarkerPriority
languageMarker和pathMarker
languageMarker和pathMarker是最先被放进promptWishList中的，经过前面的分析，我们知道在配置中，languageMarker和pathMarker都是有默认值的，因此下面的判断分支一定会走到：
if (promptOpts.languageMarker !== h.NoMarker) {
const e = newLineEnded(r.getLanguageMarker(resourceInfo));
languageMarkerId = promptWishlist.append(e, p.PromptElementKind.LanguageMarker, languageMarkerPriority);
}
if (promptOpts.pathMarker !== f.NoMarker) {
const e = newLineEnded(r.getPathMarker(resourceInfo));
if (e.length > 0) {
pathMarkerId = promptWishlist.append(e, p.PromptElementKind.PathMarker, pathMarkerPriority);
}
}这两个函数实现也比较简单，我们先来看一下getLanguageMarker：
```jsx
exports.getLanguageMarker = function (e) {
const {
languageId: t
} = e;
return -1 !== n.indexOf(t) || hasLanguageMarker(e) ? "" : t in r ? r[t] : comment(`Language: ${t}`, t);
};
```
这里首先确认了languageId，不在ignoreList当中，在copilot中，有两种语言是被排除在外的：
```jsx
const n = ["php", "plaintext"];
```
其次再看一下语言本身是否有标记语法，在这个Map中（HTML、Python、Ruby、Shell、YAML）：
```jsx
const r = {
html: "<!DOCTYPE html>",
python: "#!/usr/bin/env python3",
ruby: "#!/usr/bin/env ruby",
shellscript: "#!/bin/sh",
yaml: "# YAML data"
};
```
其余的情况就返回一行注释，类似这样：
```jsx
// Language: ${languageId}
```
getPathMarker逻辑更简单些，只是一行注释，标明文件路径（暂时搞不清楚这个信息给模型有什么用，可能路径里面包含了目录结构信息和文件名帮助模型更好进行推断？）：
```jsx
exports.getPathMarker = function (e) {
return e.relativePath ? comment(`Path: ${e.relativePath}`, e.languageId) : "";
};
```localImportContext
localImportContext的实现要复杂一点，通过上面的配置我们可以看到这个也是默认有值的，会进到下面这个分支当中：
if (promptOpts.localImportContext !== y.NoContext)
for (const e of await i.extractLocalImportContext(resourceInfo, promptOpts.fs))
promptWishlist.append(newLineEnded(e), p.PromptElementKind.ImportedFile, importedFilePriority);extractLocalImportContext是一个异步函数，让我们看一下这里面的实现：
…首先我们可以关注到的是，这个函数先判断了Typescript的语言，也就意味着当前版本的Copilot，只对ts文件的import依赖做了处理。
这个函数之所以是异步的，就是这里要拿到import语句的语法树，这个过程比较复杂，copilot是使用了wasm的方式，通过tree-sitter来解析语法树的，这个过程是异步的。
最后，copilot提取出所有的import，并且返回了所有named import对应的export代码，也就是最终索引到了依赖文件，将用到的export都作为上下文extract出来。snippets
snippets的处理是比较复杂的，在Copilot中，首先拿到了一个snippets：
…在默认的场景下，`retrievalSnippets`是空的，而`neighboringTabs`在我们前面的分析中是`eager`，所以会通过`getNeighborSnippets`去拿到这个数组。
注意这里传入了`neighborDocs`，这个是在extract的入口就传过来的，对应的代码是：
```jsx
let neighborDocs = [];
let neighborSource = new Map();
try {
const t = await u.NeighborSource.getNeighborFiles(ctx, uri, repoUserData);
neighborDocs = t.docs;
neighborSource = t.neighborSource;
} catch (t) {
telemetry.telemetryException(ctx, t, "prompt.getPromptForSource.exception");
}
```
在默认的情况下，这里拿到的fileType是`OpenTabs`，所以会默认通过VSCode拿到目前打开的tab中，包含同类型语言文件的所有内容(按访问时间排序)，对应的代码如下：…接着我们来看一下`getNeighborSnippets`的实现：…在这个实现中，我们可以得到以下关键信息：
- neighboringSnippetTypes默认为NeighboringSnippets，所以会走到`FixedWindowSizeJaccardMatcher`的逻辑里
- 返回值是根据neighborDocs的内容，过滤掉过小和过大文件，经过findMatchers拿到的结果
- 最后过滤掉score较低的，不过threshold默认为0，所以这里应该保留了所有的内容
- 根据score进行排序，选取较大的4条（numberOfSnippets默认为4）
紧接着我们就来看看`FixedWindowSizeJaccardMatcher`的逻辑：…这里的`snippetLength` 在eager的情况下默认为60，也就意味着snippet最多不超过60行。
这个类继承了`WindowedMatcher`，findMatches就在WindowedMatcher里：
```jsx
async findMatches(e, t = i.SnippetSelectionOption.BestMatch, n) {
if (t == i.SnippetSelectionOption.BestMatch) {
const t = await this.findBestMatch(e);
return t ? [t] : [];
}
return t == i.SnippetSelectionOption.TopK && (await this.findTopKMatches(e, n)) || [];
}
```
在这里第二个参数其实默认是undefined，所以默认走到BestMatch的分支：
```jsx
async findBestMatch(e) {
if (0 === e.source.length || 0 === this.referenceTokens.size) return;
const t = e.source.split("\n");
const n = this.retrieveAllSnippets(e, s.Descending);
return 0 !== n.length && 0 !== n[0].score ? {
snippet: t.slice(n[0].startLine, n[0].endLine).join("\n"),
semantics: o.SnippetSemantics.Snippet,
provider: o.SnippetProvider.NeighboringTabs,
...n[0]
} : void 0;
}
```
可以看到所谓BestMatch，就是取出`retrieveAllSnippets` 的第0条结果作为snippet返回。…这段代码的核心是根据窗口计算出不同的代码片段与当前文件的相似度，并返回排序后的片段列表。
首先这里做了个缓存处理，用来缓存已经计算过相似度的代码；
然后我们重点关注下这里的几个逻辑：
- 经过tokenize获取到当前代码片段每一行的token
- 通过getWindowsDelineations将代码分割成不同的小窗口（步长为1）
- 每个窗口的token和当前文件（referenceDoc）的token做一次相似度计算（`Jaccard`相似度）
这三个点都非常关键，我们展开来分析下：
1. **tokenize计算每一行的token**… 可以看到处理tokens其实就是分词的过程，比普通单词分割多了一步，就是过滤常见的关键词，这些关键词不影响相似度的计算（比如if、for这种）。
2. **getWindowsDelineations分割窗口**
```jsx
exports.getBasicWindowDelineations = function (e, t) {
const n = [];
const r = t.length;
if (0 == r) return [];
if (r < e) return [[0, r]];
for (let t = 0; t < r - e + 1; t++) n.push([t, t + e]);
return n;
};
```
`getWindowsDelineations` 本身逻辑并不复杂，就是根据传入的windowSize返回一个二维数组，这个二维数组的每一项都是一个起始行数和终止行数，它返回的是步长为1，在文件里面windowSize长度内的所有可能区间。
得到这些区间后，会跟当前的内容（同样windowSize）进行相似度计算，选择出相似度最高的区间内容返回，这个内容就是最终的snippet。
其中，获取当前内容的方法如下：暂无开放 Issues，或尚未同步最近议题。