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
    68                  Collections.reverse(l);
    69                  matchCollector.collect(l);
    70              }
    71              i.remove();
    72          }
    73          cpdListener.phaseUpdate(CPDListener.GROUPING);
    74          matches = matchCollector.getMatches();
    75          matchCollector = null;
    76          for (Match match: matches) {
    77              for (Iterator<TokenEntry> occurrences = match.iterator(); occurrences.hasNext();) {
    78                  TokenEntry mark = occurrences.next();
    79                  match.setLineCount(tokens.getLineCount(mark, match));
    80                  if (!occurrences.hasNext()) {
    81                      int start = mark.getBeginLine();
    82                      int end = start + match.getLineCount() - 1;
    83                      SourceCode sourceCode = source.get(mark.getTokenSrcID());
    84                      match.setSourceCodeSlice(sourceCode.getSlice(start, end));
    85                  }
    86              }
    87          }
    88          cpdListener.phaseUpdate(CPDListener.DONE);
    89      }
    90
    91      private Map<TokenEntry, Object> hash() {
    92          Map<TokenEntry, Object> markGroups = new HashMap<TokenEntry, Object>(tokens.size());
    93          for (int i = code.size() - 1; i >= 0; i--) {
    94              TokenEntry token = code.get(i);
    95              if (token != TokenEntry.EOF) {
    96                  int last = tokenAt(min, token).getIdentifier();
    97                  lastHash = MOD * lastHash + token.getIdentifier() - lastMod * last;
    98                  token.setHashCode(lastHash);
    99                  Object o = markGroups.get(token);
    100
    101                 // Note that this insertion method is worthwhile since the vast majority
    102                 // markGroup keys will have only one value.
    103                 if (o == null) {
    104                     markGroups.put(token, token);
    105                 } else if (o instanceof TokenEntry) {
    106                     List<TokenEntry> l = new ArrayList<TokenEntry>();
    107                     l.add((TokenEntry) o);
    108                     l.add(token);
    109                     markGroups.put(token, l);
    110                 } else {
    111                     List<TokenEntry> l = (List<TokenEntry>) o;
    112                     l.add(token);
    113                 }
    114             } else {
    115                 lastHash = 0;
    116                 for (int end = Math.max(0, i - min + 1); i > end; i--) {
    117                     token = code.get(i - 1);
    118                     lastHash = MOD * lastHash + token.getIdentifier();
    119                     if (token == TokenEntry.EOF) {
    120                         break;
    121                     }
    122                 }
    123             }
    124         }
    125         return markGroups;
    126     }
    127 }