1 |
| |
2 |
| |
3 |
| |
4 |
| package net.sourceforge.pmd.cpd; |
5 |
| |
6 |
| import java.util.ArrayList; |
7 |
| import java.util.Collections; |
8 |
| import java.util.HashMap; |
9 |
| import java.util.Iterator; |
10 |
| import java.util.List; |
11 |
| import java.util.Map; |
12 |
| |
13 |
| public class MatchAlgorithm { |
14 |
| |
15 |
| private final static int MOD = 37; |
16 |
| private int lastHash; |
17 |
| private int lastMod = 1; |
18 |
| |
19 |
| private List matches; |
20 |
| private Map source; |
21 |
| private Tokens tokens; |
22 |
| private List code; |
23 |
| private CPDListener cpdListener; |
24 |
| private int min; |
25 |
| |
26 |
2
| public MatchAlgorithm(Map sourceCode, Tokens tokens, int min) {
|
27 |
2
| this(sourceCode, tokens, min, new CPDNullListener());
|
28 |
| } |
29 |
| |
30 |
2
| public MatchAlgorithm(Map sourceCode, Tokens tokens, int min, CPDListener listener) {
|
31 |
2
| this.source = sourceCode;
|
32 |
2
| this.tokens = tokens;
|
33 |
2
| this.code = tokens.getTokens();
|
34 |
2
| this.min = min;
|
35 |
2
| this.cpdListener = listener;
|
36 |
2
| for (int i = 0; i < min; i++) {
|
37 |
10
| lastMod *= MOD;
|
38 |
| } |
39 |
| } |
40 |
| |
41 |
0
| public void setListener(CPDListener listener) {
|
42 |
0
| this.cpdListener = listener;
|
43 |
| } |
44 |
| |
45 |
2
| public Iterator matches() {
|
46 |
2
| return matches.iterator();
|
47 |
| } |
48 |
| |
49 |
212
| public TokenEntry tokenAt(int offset, TokenEntry m) {
|
50 |
212
| return (TokenEntry) code.get(offset + m.getIndex());
|
51 |
| } |
52 |
| |
53 |
20
| public int getMinimumTileSize() {
|
54 |
20
| return this.min;
|
55 |
| } |
56 |
| |
57 |
2
| public void findMatches() {
|
58 |
2
| cpdListener.phaseUpdate(CPDListener.HASH);
|
59 |
2
| Map markGroups = hash();
|
60 |
| |
61 |
2
| cpdListener.phaseUpdate(CPDListener.MATCH);
|
62 |
2
| MatchCollector matchCollector = new MatchCollector(this);
|
63 |
2
| for (Iterator i = markGroups.values().iterator(); i.hasNext();) {
|
64 |
60
| Object o = i.next();
|
65 |
60
| if (o instanceof List) {
|
66 |
8
| Collections.reverse((List) o);
|
67 |
8
| matchCollector.collect((List) o);
|
68 |
| } |
69 |
60
| i.remove();
|
70 |
| } |
71 |
2
| cpdListener.phaseUpdate(CPDListener.GROUPING);
|
72 |
2
| matches = matchCollector.getMatches();
|
73 |
2
| matchCollector = null;
|
74 |
2
| for (Iterator i = matches.iterator(); i.hasNext();) {
|
75 |
2
| Match match = (Match) i.next();
|
76 |
2
| for (Iterator occurrences = match.iterator(); occurrences.hasNext();) {
|
77 |
5
| TokenEntry mark = (TokenEntry) occurrences.next();
|
78 |
5
| match.setLineCount(tokens.getLineCount(mark, match));
|
79 |
5
| if (!occurrences.hasNext()) {
|
80 |
2
| int start = mark.getBeginLine();
|
81 |
2
| int end = start + match.getLineCount() - 1;
|
82 |
2
| SourceCode sourceCode = (SourceCode) source.get(mark.getTokenSrcID());
|
83 |
2
| match.setSourceCodeSlice(sourceCode.getSlice(start, end));
|
84 |
| } |
85 |
| } |
86 |
| } |
87 |
2
| cpdListener.phaseUpdate(CPDListener.DONE);
|
88 |
| } |
89 |
| |
90 |
2
| private Map hash() {
|
91 |
2
| Map markGroups = new HashMap(tokens.size());
|
92 |
2
| for (int i = code.size() - 1; i >= 0; i--) {
|
93 |
74
| TokenEntry token = (TokenEntry) code.get(i);
|
94 |
74
| if (token != TokenEntry.EOF) {
|
95 |
72
| int last = tokenAt(min, token).getIdentifier();
|
96 |
72
| lastHash = MOD * lastHash + token.getIdentifier() - lastMod * last;
|
97 |
72
| token.setHashCode(lastHash);
|
98 |
72
| Object o = markGroups.get(token);
|
99 |
| |
100 |
| |
101 |
| |
102 |
72
| if (o == null) {
|
103 |
60
| markGroups.put(token, token);
|
104 |
12
| } else if (o instanceof TokenEntry) {
|
105 |
8
| List l = new ArrayList();
|
106 |
8
| l.add(o);
|
107 |
8
| l.add(token);
|
108 |
8
| markGroups.put(token, l);
|
109 |
| } else { |
110 |
4
| List l = (List) o;
|
111 |
4
| l.add(token);
|
112 |
| } |
113 |
| } else { |
114 |
2
| lastHash = 0;
|
115 |
2
| for (int end = Math.max(0, i - min + 1); i > end; i--) {
|
116 |
8
| token = (TokenEntry) code.get(i - 1);
|
117 |
8
| lastHash = MOD * lastHash + token.getIdentifier();
|
118 |
8
| if (token == TokenEntry.EOF) {
|
119 |
0
| break;
|
120 |
| } |
121 |
| } |
122 |
| } |
123 |
| } |
124 |
2
| return markGroups;
|
125 |
| } |
126 |
| } |