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<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<>(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                 // Note that this insertion method is worthwhile since the vast majority
103                 // markGroup keys will have only one value.
104                 if (o == null) {
105                     markGroups.put(token, token);
106                 } else if (o instanceof TokenEntry) {
107                     List<TokenEntry> l = new ArrayList<>();
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 }