source.dussan.org Git - sonarqube.git/blob

   1 /*
   2  * SonarQube, open source software quality management tool.
   3  * Copyright (C) 2008-2013 SonarSource
   4  * mailto:contact AT sonarsource DOT com
   5  *
   6  * SonarQube is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 3 of the License, or (at your option) any later version.
  10  *
  11  * SonarQube is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  */
  20 package org.sonar.plugins.core.timemachine;
  21
  22 import com.google.common.annotations.VisibleForTesting;
  23 import com.google.common.base.Objects;
  24 import com.google.common.collect.*;
  25 import org.apache.commons.lang.ObjectUtils;
  26 import org.apache.commons.lang.StringUtils;
  27 import org.slf4j.Logger;
  28 import org.slf4j.LoggerFactory;
  29 import org.sonar.api.batch.*;
  30 import org.sonar.api.database.model.RuleFailureModel;
  31 import org.sonar.api.resources.Project;
  32 import org.sonar.api.resources.Resource;
  33 import org.sonar.api.rules.Violation;
  34 import org.sonar.api.violations.ViolationQuery;
  35 import org.sonar.batch.scan.LastSnapshots;
  36 import org.sonar.plugins.core.timemachine.tracking.*;
  37
  38 import javax.annotation.Nullable;
  39
  40 import java.util.*;
  41
  42 @DependsUpon({DecoratorBarriers.END_OF_VIOLATIONS_GENERATION, DecoratorBarriers.START_VIOLATION_TRACKING})
  43 @DependedUpon(DecoratorBarriers.END_OF_VIOLATION_TRACKING)
  44 public class ViolationTrackingDecorator implements Decorator {
  45
  46   private static final Logger LOG = LoggerFactory.getLogger(ViolationTrackingDecorator.class);
  47
  48   private LastSnapshots lastSnapshots;
  49   private Map<Violation, RuleFailureModel> referenceViolationsMap = Maps.newIdentityHashMap();
  50   private SonarIndex index;
  51   private Project project;
  52
  53   /**
  54    * Live collection of unmapped past violations.
  55    */
  56   private Set<RuleFailureModel> unmappedLastViolations = Sets.newHashSet();
  57
  58   public ViolationTrackingDecorator(Project project, LastSnapshots lastSnapshots, SonarIndex index) {
  59     this.lastSnapshots = lastSnapshots;
  60     this.index = index;
  61     this.project = project;
  62   }
  63
  64   public boolean shouldExecuteOnProject(Project project) {
  65     return true;
  66   }
  67
  68   public void decorate(Resource resource, DecoratorContext context) {
  69     LOG.debug("ViolationTracking : " + resource);
  70
  71     referenceViolationsMap.clear();
  72
  73     ViolationQuery violationQuery = ViolationQuery.create().forResource(resource).setSwitchMode(ViolationQuery.SwitchMode.BOTH);
  74     if (context.getViolations(violationQuery).isEmpty()) {
  75       return;
  76     }
  77
  78     String source = index.getSource(resource);
  79
  80     // Load new violations
  81     List<Violation> newViolations = prepareNewViolations(context, source);
  82
  83     // Load the violations of the last available analysis
  84     List<RuleFailureModel> referenceViolations = lastSnapshots.getViolations(resource);
  85
  86     // Map new violations with old ones
  87     mapViolations(newViolations, referenceViolations, source, resource);
  88   }
  89
  90   private List<Violation> prepareNewViolations(DecoratorContext context, String source) {
  91     List<Violation> result = Lists.newArrayList();
  92     List<String> checksums = SourceChecksum.lineChecksumsOfFile(source);
  93     for (Violation violation : context.getViolations()) {
  94       violation.setChecksum(SourceChecksum.getChecksumForLine(checksums, violation.getLineId()));
  95       result.add(violation);
  96     }
  97     return result;
  98   }
  99
 100   public RuleFailureModel getReferenceViolation(Violation violation) {
 101     return referenceViolationsMap.get(violation);
 102   }
 103
 104   @VisibleForTesting
 105   Map<Violation, RuleFailureModel> mapViolations(List<Violation> newViolations, @Nullable List<RuleFailureModel> lastViolations) {
 106     return mapViolations(newViolations, lastViolations, null, null);
 107   }
 108
 109   @VisibleForTesting
 110   Map<Violation, RuleFailureModel> mapViolations(List<Violation> newViolations, @Nullable List<RuleFailureModel> lastViolations,
 111                                                  @Nullable String source, @Nullable Resource resource) {
 112     boolean hasLastScan = false;
 113     Multimap<Integer, RuleFailureModel> lastViolationsByRule = LinkedHashMultimap.create();
 114
 115     if (lastViolations != null) {
 116       hasLastScan = true;
 117       unmappedLastViolations.addAll(lastViolations);
 118
 119       for (RuleFailureModel lastViolation : lastViolations) {
 120         lastViolationsByRule.put(lastViolation.getRuleId(), lastViolation);
 121       }
 122
 123       // Match the permanent id of the violation. This id is for example set explicitly when injecting manual violations
 124       for (Violation newViolation : newViolations) {
 125         mapViolation(newViolation,
 126           findLastViolationWithSamePermanentId(newViolation, lastViolationsByRule.get(newViolation.getRule().getId())),
 127           lastViolationsByRule, referenceViolationsMap);
 128       }
 129
 130       // Try first to match violations on same rule with same line and with same checksum (but not necessarily with same message)
 131       for (Violation newViolation : newViolations) {
 132         if (isNotAlreadyMapped(newViolation)) {
 133           mapViolation(newViolation,
 134             findLastViolationWithSameLineAndChecksum(newViolation, lastViolationsByRule.get(newViolation.getRule().getId())),
 135             lastViolationsByRule, referenceViolationsMap);
 136         }
 137       }
 138     }
 139
 140     // If each new violation matches an old one we can stop the matching mechanism
 141     if (referenceViolationsMap.size() != newViolations.size()) {
 142       if (source != null && resource != null && hasLastScan) {
 143         String referenceSource = lastSnapshots.getSource(resource);
 144         if (referenceSource != null) {
 145           HashedSequence<StringText> hashedReference = HashedSequence.wrap(new StringText(referenceSource), StringTextComparator.IGNORE_WHITESPACE);
 146           HashedSequence<StringText> hashedSource = HashedSequence.wrap(new StringText(source), StringTextComparator.IGNORE_WHITESPACE);
 147           HashedSequenceComparator<StringText> hashedComparator = new HashedSequenceComparator<StringText>(StringTextComparator.IGNORE_WHITESPACE);
 148
 149           ViolationTrackingBlocksRecognizer rec = new ViolationTrackingBlocksRecognizer(hashedReference, hashedSource, hashedComparator);
 150
 151           Multimap<Integer, Violation> newViolationsByLines = newViolationsByLines(newViolations, rec);
 152           Multimap<Integer, RuleFailureModel> lastViolationsByLines = lastViolationsByLines(unmappedLastViolations, rec);
 153
 154           RollingHashSequence<HashedSequence<StringText>> a = RollingHashSequence.wrap(hashedReference, hashedComparator, 5);
 155           RollingHashSequence<HashedSequence<StringText>> b = RollingHashSequence.wrap(hashedSource, hashedComparator, 5);
 156           RollingHashSequenceComparator<HashedSequence<StringText>> cmp = new RollingHashSequenceComparator<HashedSequence<StringText>>(hashedComparator);
 157
 158           Map<Integer, HashOccurrence> map = Maps.newHashMap();
 159
 160           for (Integer line : lastViolationsByLines.keySet()) {
 161             int hash = cmp.hash(a, line - 1);
 162             HashOccurrence hashOccurrence = map.get(hash);
 163             if (hashOccurrence == null) {
 164               // first occurrence in A
 165               hashOccurrence = new HashOccurrence();
 166               hashOccurrence.lineA = line;
 167               hashOccurrence.countA = 1;
 168               map.put(hash, hashOccurrence);
 169             } else {
 170               hashOccurrence.countA++;
 171             }
 172           }
 173
 174           for (Integer line : newViolationsByLines.keySet()) {
 175             int hash = cmp.hash(b, line - 1);
 176             HashOccurrence hashOccurrence = map.get(hash);
 177             if (hashOccurrence != null) {
 178               hashOccurrence.lineB = line;
 179               hashOccurrence.countB++;
 180             }
 181           }
 182
 183           for (HashOccurrence hashOccurrence : map.values()) {
 184             if (hashOccurrence.countA == 1 && hashOccurrence.countB == 1) {
 185               // Guaranteed that lineA has been moved to lineB, so we can map all violations on lineA to all violations on lineB
 186               LOG.debug("*** Guaranteed that lineA has been moved to lineB, so we can map all issues on lineA to all issues on lineB");
 187               map(newViolationsByLines.get(hashOccurrence.lineB), lastViolationsByLines.get(hashOccurrence.lineA), lastViolationsByRule);
 188               lastViolationsByLines.removeAll(hashOccurrence.lineA);
 189               newViolationsByLines.removeAll(hashOccurrence.lineB);
 190             }
 191           }
 192
 193           // Check if remaining number of lines exceeds threshold
 194           if (lastViolationsByLines.keySet().size() * newViolationsByLines.keySet().size() < 250000) {
 195             List<LinePair> possibleLinePairs = Lists.newArrayList();
 196             for (Integer oldLine : lastViolationsByLines.keySet()) {
 197               for (Integer newLine : newViolationsByLines.keySet()) {
 198                 int weight = rec.computeLengthOfMaximalBlock(oldLine - 1, newLine - 1);
 199                 possibleLinePairs.add(new LinePair(oldLine, newLine, weight));
 200               }
 201             }
 202             Collections.sort(possibleLinePairs, LINE_PAIR_COMPARATOR);
 203             for (LinePair linePair : possibleLinePairs) {
 204               // High probability that lineA has been moved to lineB, so we can map all violations on lineA to all violations on lineB
 205               LOG.debug("*** High probability that lineA has been moved to lineB, so we can map all Issues on lineA to all Issues on lineB");
 206               map(newViolationsByLines.get(linePair.lineB), lastViolationsByLines.get(linePair.lineA), lastViolationsByRule);
 207             }
 208           }
 209         }
 210       }
 211
 212       // Try then to match violations on same rule with same message and with same checksum
 213       for (Violation newViolation : newViolations) {
 214         if (isNotAlreadyMapped(newViolation)) {
 215           LOG.debug("*** Try then to match issues on same rule with same message and with same checksum");
 216           mapViolation(newViolation,
 217             findLastViolationWithSameChecksumAndMessage(newViolation, lastViolationsByRule.get(newViolation.getRule().getId())),
 218             lastViolationsByRule, referenceViolationsMap);
 219         }
 220       }
 221
 222       // Try then to match violations on same rule with same line and with same message
 223       for (Violation newViolation : newViolations) {
 224         if (isNotAlreadyMapped(newViolation)) {
 225           LOG.debug("*** Try then to match issues on same rule with same line and with same message");
 226           mapViolation(newViolation,
 227             findLastViolationWithSameLineAndMessage(newViolation, lastViolationsByRule.get(newViolation.getRule().getId())),
 228             lastViolationsByRule, referenceViolationsMap);
 229         }
 230       }
 231
 232       // Last check: match violation if same rule and same checksum but different line and different message
 233       // See SONAR-2812
 234       for (Violation newViolation : newViolations) {
 235         if (isNotAlreadyMapped(newViolation)) {
 236           LOG.debug("*** Last check: match issue if same rule and same checksum but different line and different message");
 237           mapViolation(newViolation,
 238             findLastViolationWithSameChecksum(newViolation, lastViolationsByRule.get(newViolation.getRule().getId())),
 239             lastViolationsByRule, referenceViolationsMap);
 240         }
 241       }
 242     }
 243
 244     unmappedLastViolations.clear();
 245     return referenceViolationsMap;
 246   }
 247
 248   private void map(Collection<Violation> newViolations, Collection<RuleFailureModel> lastViolations, Multimap<Integer, RuleFailureModel> lastViolationsByRule) {
 249     for (Violation newViolation : newViolations) {
 250       if (isNotAlreadyMapped(newViolation)) {
 251         for (RuleFailureModel pastViolation : lastViolations) {
 252           if (isNotAlreadyMapped(pastViolation) && Objects.equal(newViolation.getRule().getId(), pastViolation.getRuleId())) {
 253             LOG.debug("mapIssue newViolation : " + newViolation + " with pastViolation : " + pastViolation);
 254             mapViolation(newViolation, pastViolation, lastViolationsByRule, referenceViolationsMap);
 255             break;
 256           } else {
 257             LOG.debug("Not mapIssue newViolation : " + newViolation + " with pastViolation : " + pastViolation);
 258           }
 259         }
 260       }
 261     }
 262   }
 263
 264   private Multimap<Integer, Violation> newViolationsByLines(Collection<Violation> newViolations, ViolationTrackingBlocksRecognizer rec) {
 265     Multimap<Integer, Violation> newViolationsByLines = LinkedHashMultimap.create();
 266     for (Violation newViolation : newViolations) {
 267       if (isNotAlreadyMapped(newViolation)) {
 268         if (rec.isValidLineInSource(newViolation.getLineId())) {
 269           newViolationsByLines.put(newViolation.getLineId(), newViolation);
 270         }
 271       }
 272     }
 273     return newViolationsByLines;
 274   }
 275
 276   private Multimap<Integer, RuleFailureModel> lastViolationsByLines(Collection<RuleFailureModel> lastViolations, ViolationTrackingBlocksRecognizer rec) {
 277     Multimap<Integer, RuleFailureModel> lastViolationsByLines = LinkedHashMultimap.create();
 278     for (RuleFailureModel pastViolation : lastViolations) {
 279       if (rec.isValidLineInReference(pastViolation.getLine())) {
 280         lastViolationsByLines.put(pastViolation.getLine(), pastViolation);
 281       }
 282     }
 283     return lastViolationsByLines;
 284   }
 285
 286   private static final Comparator<LinePair> LINE_PAIR_COMPARATOR = new Comparator<LinePair>() {
 287     public int compare(LinePair o1, LinePair o2) {
 288       return o2.weight - o1.weight;
 289     }
 290   };
 291
 292   static class LinePair {
 293     int lineA;
 294     int lineB;
 295     int weight;
 296
 297     public LinePair(int lineA, int lineB, int weight) {
 298       this.lineA = lineA;
 299       this.lineB = lineB;
 300       this.weight = weight;
 301     }
 302   }
 303
 304   static class HashOccurrence {
 305     int lineA;
 306     int lineB;
 307     int countA;
 308     int countB;
 309   }
 310
 311   private boolean isNotAlreadyMapped(RuleFailureModel pastViolation) {
 312     return unmappedLastViolations.contains(pastViolation);
 313   }
 314
 315   private boolean isNotAlreadyMapped(Violation newViolation) {
 316     return !referenceViolationsMap.containsKey(newViolation);
 317   }
 318
 319   private RuleFailureModel findLastViolationWithSameChecksum(Violation newViolation, Collection<RuleFailureModel> lastViolations) {
 320     for (RuleFailureModel pastViolation : lastViolations) {
 321       if (isSameChecksum(newViolation, pastViolation)) {
 322         return pastViolation;
 323       }
 324     }
 325     return null;
 326   }
 327
 328   private RuleFailureModel findLastViolationWithSameLineAndMessage(Violation newViolation, Collection<RuleFailureModel> lastViolations) {
 329     for (RuleFailureModel pastViolation : lastViolations) {
 330       if (isSameLine(newViolation, pastViolation) && isSameMessage(newViolation, pastViolation)) {
 331         return pastViolation;
 332       }
 333     }
 334     return null;
 335   }
 336
 337   private RuleFailureModel findLastViolationWithSameChecksumAndMessage(Violation newViolation, Collection<RuleFailureModel> lastViolations) {
 338     for (RuleFailureModel pastViolation : lastViolations) {
 339       if (isSameChecksum(newViolation, pastViolation) && isSameMessage(newViolation, pastViolation)) {
 340         return pastViolation;
 341       }
 342     }
 343     return null;
 344   }
 345
 346   private RuleFailureModel findLastViolationWithSameLineAndChecksum(Violation newViolation, Collection<RuleFailureModel> lastViolations) {
 347     for (RuleFailureModel pastViolation : lastViolations) {
 348       if (isSameLine(newViolation, pastViolation) && isSameChecksum(newViolation, pastViolation)) {
 349         return pastViolation;
 350       }
 351     }
 352     return null;
 353   }
 354
 355   private RuleFailureModel findLastViolationWithSamePermanentId(Violation newViolation, Collection<RuleFailureModel> lastViolations) {
 356     for (RuleFailureModel pastViolation : lastViolations) {
 357       if (isSamePermanentId(newViolation, pastViolation)) {
 358         return pastViolation;
 359       }
 360     }
 361     return null;
 362   }
 363
 364   private boolean isSameChecksum(Violation newViolation, RuleFailureModel pastViolation) {
 365     return StringUtils.equals(pastViolation.getChecksum(), newViolation.getChecksum());
 366   }
 367
 368   private boolean isSameLine(Violation newViolation, RuleFailureModel pastViolation) {
 369     return ObjectUtils.equals(pastViolation.getLine(), newViolation.getLineId());
 370   }
 371
 372   private boolean isSameMessage(Violation newViolation, RuleFailureModel pastViolation) {
 373     return StringUtils.equals(RuleFailureModel.abbreviateMessage(newViolation.getMessage()), pastViolation.getMessage());
 374   }
 375
 376   private boolean isSamePermanentId(Violation newViolation, RuleFailureModel pastViolation) {
 377     return newViolation.getPermanentId() != null && newViolation.getPermanentId().equals(pastViolation.getPermanentId());
 378   }
 379
 380   private void mapViolation(Violation newViolation, RuleFailureModel pastViolation,
 381                             Multimap<Integer, RuleFailureModel> lastViolationsByRule, Map<Violation, RuleFailureModel> violationMap) {
 382     if (pastViolation != null) {
 383       LOG.debug("Mapping with old violation from newViolation : " + newViolation + " and pastViolation : " + pastViolation);
 384
 385       newViolation.setCreatedAt(pastViolation.getCreatedAt());
 386       newViolation.setPermanentId(pastViolation.getPermanentId());
 387       newViolation.setSwitchedOff(pastViolation.isSwitchedOff());
 388       newViolation.setPersonId(pastViolation.getPersonId());
 389       newViolation.setNew(false);
 390       lastViolationsByRule.remove(newViolation.getRule().getId(), pastViolation);
 391       violationMap.put(newViolation, pastViolation);
 392       unmappedLastViolations.remove(pastViolation);
 393     } else {
 394       LOG.debug("No old violation, creating new one with newViolation : " + newViolation + " and pastViolation : " + pastViolation);
 395
 396       newViolation.setNew(true);
 397       newViolation.setCreatedAt(project.getAnalysisDate());
 398     }
 399   }
 400
 401   @Override
 402   public String toString() {
 403     return getClass().getSimpleName();
 404   }
 405
 406 }