[CPD] How to determine the code duplication?

[cyw3]

I want to know about CPD's principle.

I guess:

1. base on tokens's hashcode?
2. base on code's AST?

[cyw3]

And if it base on tokens's hashcode, how can i get the hashcode from the cpd?

[jsotuyod]

@cyw3 that's an interesting question, with a hateful answer: it depends.

At the core, CPD takes tokens from a "lexer source", and hashes the contents on a rolling window of the requested length via the --minimum-tokens argument. The general matching algorithm is implemented on MatchAlgorithm.

However, this "lexer source" is provided by each language module, and the particulars may vary.

The basic lexer (AnyTokenizer) just tokenizes the text of the analyzed file with no knowledge of the grammar itself. No language officially supported by PMD uses this, but it can be used to analyze any text file normalizing whitespace.

Officially supported languages use actual lexers for the language, which not only normalizes whitespace, but actually gives us one extra benefit: we can ignore comments.

Moreover, some languages further refine these token sources, allowing extra behaviors, such as:

1. normalizing names of identifiers, to detect identical code where only names of variables / methods change (--ignore-identifiers on Java)
2. normalizing constant values of all types, to detect identical code where only constants are different (--ignore-literals on Java)
3. discarding annotation tokens when comparing code (--ignore-annotations on Java)
4. discarding using XXX directives when comparing code (--ignore-usings on C#)
5. discarding blocks under conditional compilation when comparing code (--skip-blocks-pattern on C/C++)

So, bottom line:

1. we hash a rolling window of tokens
2. tokenization is based on language features
3. additional logic may be applied to sanitize / alter the token stream to be harder on analysis or avoid reporting on code that has no way to be de-duped.

As for your last question, the hash of each window is not part of the public API, just computed during analysis and discarded immediately afterwards. It can be obtained directly from the TokenEntry.hashCode() method; but you would have to manually run CPD logic, and revisit the token stream before shutting down to be able to do so.