View Javadoc

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 }