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