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 }