하위 트리를 사용하여 유사한 코드 섹션 찾기

Question

나는 Ira D. Baxter 외 다수가 Clone Detection using Abstract Syntax Trees이라는 제목의이 논문을 읽었습니다. 원칙적으로

, 하위 트리 클론 찾는 은 간단하다 : 평등에 대한 다른 모든 하위 트리에있는 모든 하위 트리를 비교 내가 아래에 재생 종이에서 단락이있다. 연습에서 몇 가지 문제가 발생합니다. 니어 - 근처 클론 감지, 하위 클론 및 배율. ...

, 아차에게 클론의 위치를 ​​전체 하위 트리 에 해싱 좋은 해시 기능은 트리의 모든 요소를 ​​포함 정확하게 때문에 실패하고, 따라서 다른 버킷에 작은 차이 머릿단을 정렬합니다. 우리는 인위적으로 나쁜 해시 함수을 선택하여이 문제를 해결했습니다. 이 기능은 에 특징이있어서 근처의 주요 클레임에서 찾을 수있는 기본 속성 이 보존됩니다. 미스 클론은 일반적으로 이며, 절차를 복사하여 붙여 넣은 다음 작은 수정 사항을 붙여 넣습니다. 이러한 수정은 은 일반적으로 복사 된 코드 조각과 관련된 트리의 모양에 작은 변경을 생성합니다. 따라서 은 이런 종류의 니어 미스 클론은 종종 다른 하위 나무를 가지고 있다고 주장합니다. 작은 하위 나무. 이 관찰을 바탕으로 작은 하위 트리를 무시하는 해시 함수는 goodchoice입니다. 여기에 제시된 실험에서는 으로 식별자 만 무시하는 기능을 사용했습니다 (트리에서 남음). 따라서 우리의 해싱 함수는 비교를 위해 동일한 해시 저장소에 비슷한 모듈러 식별자 인 인 트리를 넣습니다.

나는이 글에서 설명한 기술을 구현하기 위해 노력하고 있지만 (즉, 종이의 시작 부분에 불행히도)이 한 단락을 이해하려고에 갇혀 있어요. 나는 단락이 말하는 것을 이해하지만 제작자는 해시 함수를 선택하거나 AST를 실제로 해싱하는 방법을 언급하지 않습니다. 누군가 구현의 관점에서 간단한 예를 들어 설명해 주시겠습니까?

Answer 1

저자 자신이 응답해야하는 음영. StackOverflow가 훌륭하지 않습니다 : -?

많은 수의 버킷에 입력 값을 균등하게 분배하는 한 해시 함수의 포인트는 중요하지 않습니다. 전체 트리에 적용 할 수있는 해시 함수가 필요합니다. 이와 같은 일반적인 기술은 트리를 가능한 한 순차적으로 (예 : 순서대로 트리를 방문하여) 직렬화 한 다음 생성되는 값 (트리 노드)의 스트림에 해시 함수를 적용하는 것입니다. (이 아이디어는 원래의 CloneDR에 대한 영감이었던 일반적인 하위 표현식을 찾는 컴파일러 관련 자료에서 나온 것입니다.) 이것이 명확하지 않으면 복잡한 데이터 구조에 해시 함수를 적용하는 방법을 이해하는 데 더 많은 에너지를 소비해야합니다. hashing에 Wikipedia는 시작할 것이다 좋은 장소이다; 그것이 충분하지 않다면 알고리즘에 관한 책을 찾고 공부해야합니다.

해시 함수에 적용되는 것은 사용자에게 달려 있습니다. 이 논문에서 작성한 요점은 AST의 식별자 잎을 무시하는 해시 함수를 계산할 수 있다는 점입니다. 그러면 AST의 구조는 같지만 식별자가 다른 트리가 동일한 버킷에 해시됩니다. 따라서 유사한 모듈러 식별자 인 트리는 동일한 해시 버킷에서 발생하기 때문에 쉽게 일치됩니다.

물론 모듈로 식별자를 매치하는 것만으로 전체 클론 탐지 알고리즘이 훨씬 더 많습니다. 결과를보고하는 매개 변수화 된 시퀀스 (이 점을 종이의 가장 중요한 점)과 일치시키는 것에 대해 걱정할 필요가 있습니다. 물론 적용 할 언어에 상관없이 고품질의 언어 파서가 필요합니다.

CloneDR의 결과를 다양한 언어로 볼 수 있습니다.

Answer 2

두 개의 AST가 인간의 눈에 "복제본"이라는 것을 알고 있다면 해시 값도 동일해야합니다.

예를 들어 식별자 이름을 상수로, 모든 문자열을 다른 상수로 해시하는 것은 실제로 식별자 이름을 해시의 중요한 부분으로 사용하는 대신 변수 이름을 바꿔서 속이지 않도록합니다.

또는 교환 가능한 해시를 표현식으로 사용하십시오. a + b와 b + a가 같은 해시 값을 얻는 지 확인하십시오.

hash VariableName = 0x12345678 
hash IntegerConstant = 0xff77ff77 
hash x + y = (hash x) + (hash y) 
hash (x) = (hash x) <<< 13 
hash x * y = (hash x) xor (hash y) 

등 : 변수, 정수 연산자 괄호를 포함하는 산술 표현식은

예