1 /***
2 * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
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 public MatchAlgorithm(Map sourceCode, Tokens tokens, int min) {
27 this(sourceCode, tokens, min, new CPDNullListener());
28 }
29
30 public MatchAlgorithm(Map 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 void findMatches() {
46 cpdListener.phaseUpdate(CPDListener.HASH);
47 Map markGroups = hash();
48
49 cpdListener.phaseUpdate(CPDListener.MATCH);
50 MatchCollector coll = new MatchCollector(this);
51 for (Iterator i = markGroups.values().iterator(); i.hasNext();) {
52 Object o = i.next();
53 if (o instanceof List) {
54 Collections.reverse((List) o);
55 coll.collect(min, (List) o);
56 }
57 i.remove();
58 }
59
60 cpdListener.phaseUpdate(CPDListener.GROUPING);
61 matches = coll.getMatches();
62 coll = null;
63
64 for (Iterator i = matches(); i.hasNext();) {
65 Match match = (Match) i.next();
66 for (Iterator occurrences = match.iterator(); occurrences.hasNext();) {
67 TokenEntry mark = (TokenEntry) occurrences.next();
68 match.setLineCount(tokens.getLineCount(mark, match));
69 if (!occurrences.hasNext()) {
70 int start = mark.getBeginLine();
71 int end = start + match.getLineCount() - 1;
72 SourceCode sourceCode = (SourceCode) source.get(mark.getTokenSrcID());
73 match.setSourceCodeSlice(sourceCode.getSlice(start, end));
74 }
75 }
76 }
77 cpdListener.phaseUpdate(CPDListener.DONE);
78 }
79
80 private Map hash() {
81 Map markGroups = new HashMap(tokens.size());
82 for (int i = code.size() - 1; i >= 0; i--) {
83 TokenEntry token = (TokenEntry) code.get(i);
84 if (token != TokenEntry.EOF) {
85 int last = tokenAt(min, token).getIdentifier();
86 lastHash = MOD * lastHash + token.getIdentifier() - lastMod * last;
87 token.setHashCode(lastHash);
88 Object o = markGroups.get(token);
89 if (o == null) {
90 markGroups.put(token, token);
91 } else if (o instanceof TokenEntry) {
92 List l = new ArrayList();
93 l.add(o);
94 l.add(token);
95 markGroups.put(token, l);
96 } else {
97 List l = (List) o;
98 l.add(token);
99 }
100 } else {
101 lastHash = 0;
102 for (int end = Math.max(0, i - min + 1); i > end; i--) {
103 token = (TokenEntry) code.get(i - 1);
104 lastHash = MOD * lastHash + token.getIdentifier();
105 if (token == TokenEntry.EOF) {
106 break;
107 }
108 }
109 }
110 }
111 return markGroups;
112 }
113
114 public Iterator matches() {
115 return matches.iterator();
116 }
117
118 public TokenEntry tokenAt(int offset, TokenEntry m) {
119 return (TokenEntry) code.get(offset + m.getIndex());
120 }
121
122 }
This page was automatically generated by Maven