如何为代码片段制定哈希算法？

Question

我想制作一种算法，基于一些哈希算法，可以在迭代源代码时检测代码片段。

例如，这里是来自片段着色器的简短代码片段：

vec3 Fresnel(vec3 F0, float cosTheta) {
    float foo1;
    float foo2;
    return F0 + (vec3(1, 1, 1) - F0) * pow(1-cosTheta, 5);
}

我想对这几行进行哈希处理，然后根据哈希值，检查其他代码片段是否与上面的相同。当然，变量的名称和参数的顺序并不重要，例如

foo1

和

foo2

的顺序。

我知道像这样的哈希算法是可能的，但我不知道从哪里开始。

Answer 1

这有两个方面 - 第一个方面是弄清楚如何识别要索引的代码片段。 这可能非常复杂，您可能想要也可能不想要重叠/嵌套的代码片段（例如，对于返回行或其中的表达式，作为一个代码片段，而整个菲涅尔函数是另一个代码片段。无论如何，我会把这方面留给你去解决散列部分。

一旦您有了某种方法来迭代代码片段，您就可以简单地在该片段的源代码上调用哈希函数：因为代码片段是一串文本，所以这在大多数语言中都很容易完成 - 例如在 C++ 中你可以做

std::hash<std::string_view>{}(my_code_snippet_string_view)

。

“当然，变量的名称和参数的顺序并不重要，就像 foo1 和 foo2 的顺序一样。”表明您希望首先对代码进行一些标准化/规范化过程（例如，重新格式化它、用单个空格替换任意连续的空格、删除注释、用递增占位符 __1、__2 替换标识符，也许对没有的语句进行排序必要的排序等），以便功能等效的代码将产生相同的哈希值。 这将高度依赖于语言，并且为了做好它，您可能需要使用某种方式的解析器。 完美地做到这一点很难，但是您无需做太多工作就可以获得足够有用的结果来满足您的目的。 （在 C++ 中，极端情况下，您可以使用 clang-tools 将代码转换为 AST，对其进行各种转换，但您不仅需要代码片段，还需要所有早期代码才能使其成为有效的翻译单元） .