SONAR-3072 Add greedy algorithm to track violations based on blocks

8 files changed, 305 insertions, 13 deletions

diff --git a/plugins/sonar-core-plugin/pom.xml b/plugins/sonar-core-plugin/pom.xml
index 88d2101ab66..987bb0e93a8 100644
--- a/plugins/sonar-core-plugin/pom.xml
+++ b/plugins/sonar-core-plugin/pom.xml
@@ -15,6 +15,11 @@
   <dependencies>
     <dependency>
       <groupId>org.codehaus.sonar</groupId>
+      <artifactId>sonar-diff</artifactId>
+      <version>${project.version}</version>
+    </dependency>
+    <dependency>
+      <groupId>org.codehaus.sonar</groupId>
       <artifactId>sonar-plugin-api</artifactId>
       <scope>provided</scope>
     </dependency>
diff --git a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ReferenceAnalysis.java b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ReferenceAnalysis.java
index 224b4bd954a..c5a44fd82b0 100644
--- a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ReferenceAnalysis.java
+++ b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ReferenceAnalysis.java
@@ -24,9 +24,11 @@ import org.sonar.api.database.DatabaseSession;
 import org.sonar.api.database.model.ResourceModel;
 import org.sonar.api.database.model.RuleFailureModel;
 import org.sonar.api.database.model.Snapshot;
+import org.sonar.api.database.model.SnapshotSource;
 import org.sonar.api.resources.Resource;
 
 import javax.persistence.Query;
+
 import java.util.Collections;
 import java.util.List;
 
@@ -46,9 +48,20 @@ public class ReferenceAnalysis implements BatchExtension {
     return Collections.emptyList();
   }
 
-  Snapshot getSnapshot(Resource resource) {
+  public String getSource(Resource resource) {
+    Snapshot snapshot = getSnapshot(resource);
+    if (snapshot != null) {
+      SnapshotSource source = session.getSingleResult(SnapshotSource.class, "snapshotId", snapshot.getId());
+      if (source != null) {
+        return source.getData();
+      }
+    }
+    return "";
+  }
+
+  private Snapshot getSnapshot(Resource resource) {
     Query query = session.createQuery("from " + Snapshot.class.getSimpleName() + " s where s.last=:last and s.resourceId=(select r.id from "
-        + ResourceModel.class.getSimpleName() + " r where r.key=:key)");
+      + ResourceModel.class.getSimpleName() + " r where r.key=:key)");
     query.setParameter("key", resource.getEffectiveKey());
     query.setParameter("last", Boolean.TRUE);
     return session.getSingleResult(query, null);
diff --git a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationPair.java b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationPair.java
new file mode 100644
index 00000000000..92200326cb1
--- /dev/null
+++ b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationPair.java
@@ -0,0 +1,54 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2012 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.plugins.core.timemachine;
+
+import org.sonar.api.database.model.RuleFailureModel;
+import org.sonar.api.rules.Violation;
+
+import java.util.Comparator;
+
+public class ViolationPair {
+
+  private final RuleFailureModel pastViolation;
+  private final Violation newViolation;
+  private final int weight;
+
+  public ViolationPair(RuleFailureModel pastViolation, Violation newViolation, int weight) {
+    this.pastViolation = pastViolation;
+    this.newViolation = newViolation;
+    this.weight = weight;
+  }
+
+  public Violation getNewViolation() {
+    return newViolation;
+  }
+
+  public RuleFailureModel getPastViolation() {
+    return pastViolation;
+  }
+
+  public static final Comparator<ViolationPair> COMPARATOR = new Comparator<ViolationPair>() {
+    @Override
+    public int compare(ViolationPair o1, ViolationPair o2) {
+      return o2.weight - o1.weight;
+    }
+  };
+
+}
diff --git a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizer.java b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizer.java
new file mode 100644
index 00000000000..0ba647693d9
--- /dev/null
+++ b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizer.java
@@ -0,0 +1,75 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2012 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.plugins.core.timemachine;
+
+import org.sonar.diff.HashedSequence;
+import org.sonar.diff.HashedSequenceComparator;
+import org.sonar.diff.StringText;
+import org.sonar.diff.StringTextComparator;
+
+public class ViolationTrackingBlocksRecognizer {
+
+  private final HashedSequence<StringText> a;
+  private final HashedSequence<StringText> b;
+  private final HashedSequenceComparator<StringText> cmp;
+
+  public ViolationTrackingBlocksRecognizer(String referenceSource, String source) {
+    this(new StringText(referenceSource), new StringText(source), StringTextComparator.IGNORE_WHITESPACE);
+  }
+
+  private ViolationTrackingBlocksRecognizer(StringText a, StringText b, StringTextComparator cmp) {
+    this.a = wrap(a, cmp);
+    this.b = wrap(b, cmp);
+    this.cmp = new HashedSequenceComparator<StringText>(cmp);
+  }
+
+  private static HashedSequence<StringText> wrap(StringText seq, StringTextComparator cmp) {
+    int size = seq.length();
+    int[] hashes = new int[size];
+    for (int i = 0; i < size; i++) {
+      hashes[i] = cmp.hash(seq, i);
+    }
+    return new HashedSequence<StringText>(seq, hashes);
+  }
+
+  public int computeLengthOfMaximalBlock(int startA, int startB) {
+    if (!cmp.equals(a, startA, b, startB)) {
+      return 0;
+    }
+    int length = 0;
+    int ai = startA;
+    int bi = startB;
+    while (ai < a.length() && bi < b.length() && cmp.equals(a, ai, b, bi)) {
+      ai++;
+      bi++;
+      length++;
+    }
+    ai = startA;
+    bi = startB;
+    while (ai >= 0 && bi >= 0 && cmp.equals(a, ai, b, bi)) {
+      ai--;
+      bi--;
+      length++;
+    }
+    // Note that position (startA, startB) was counted twice
+    return length - 1;
+  }
+
+}
diff --git a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingDecorator.java b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingDecorator.java
index dd175ec7a65..705069235c9 100644
--- a/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingDecorator.java
+++ b/plugins/sonar-core-plugin/src/main/java/org/sonar/plugins/core/timemachine/ViolationTrackingDecorator.java
@@ -19,10 +19,8 @@
  */
 package org.sonar.plugins.core.timemachine;
 
-import com.google.common.collect.LinkedHashMultimap;
-import com.google.common.collect.Lists;
-import com.google.common.collect.Maps;
-import com.google.common.collect.Multimap;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.*;
 import org.apache.commons.lang.ObjectUtils;
 import org.apache.commons.lang.StringUtils;
 import org.sonar.api.batch.*;
@@ -32,9 +30,7 @@ import org.sonar.api.resources.Resource;
 import org.sonar.api.rules.Violation;
 import org.sonar.api.violations.ViolationQuery;
 
-import java.util.Collection;
-import java.util.List;
-import java.util.Map;
+import java.util.*;
 
 @DependsUpon({DecoratorBarriers.END_OF_VIOLATIONS_GENERATION, DecoratorBarriers.START_VIOLATION_TRACKING})
 @DependedUpon(DecoratorBarriers.END_OF_VIOLATION_TRACKING)
@@ -65,8 +61,13 @@ public class ViolationTrackingDecorator implements Decorator {
       // Load reference violations
       List<RuleFailureModel> referenceViolations = referenceAnalysis.getViolations(resource);
 
+      // SONAR-3072 Construct blocks recognizer based on reference source
+      String referenceSource = referenceAnalysis.getSource(resource);
+      String source = index.getSource(context.getResource());
+      ViolationTrackingBlocksRecognizer rec = new ViolationTrackingBlocksRecognizer(referenceSource, source);
+
       // Map new violations with old ones
-      mapViolations(newViolations, referenceViolations);
+      mapViolations(newViolations, referenceViolations, rec);
     }
   }
 
@@ -84,7 +85,12 @@ public class ViolationTrackingDecorator implements Decorator {
     return referenceViolationsMap.get(violation);
   }
 
+  @VisibleForTesting
   Map<Violation, RuleFailureModel> mapViolations(List<Violation> newViolations, List<RuleFailureModel> pastViolations) {
+    return mapViolations(newViolations, pastViolations, null);
+  }
+
+  private Map<Violation, RuleFailureModel> mapViolations(List<Violation> newViolations, List<RuleFailureModel> pastViolations, ViolationTrackingBlocksRecognizer rec) {
     Multimap<Integer, RuleFailureModel> pastViolationsByRule = LinkedHashMultimap.create();
     for (RuleFailureModel pastViolation : pastViolations) {
       pastViolationsByRule.put(pastViolation.getRuleId(), pastViolation);
@@ -97,7 +103,6 @@ public class ViolationTrackingDecorator implements Decorator {
           pastViolationsByRule, referenceViolationsMap);
     }
 
-
     // Try first to match violations on same rule with same line and with same checkum (but not necessarily with same message)
     for (Violation newViolation : newViolations) {
       if (isNotAlreadyMapped(newViolation, referenceViolationsMap)) {
@@ -109,7 +114,32 @@ public class ViolationTrackingDecorator implements Decorator {
 
     // If each new violation matches an old one we can stop the matching mechanism
     if (referenceViolationsMap.size() != newViolations.size()) {
-      // Try then to match violations on same rule with same message and with same checkum
+      // FIXME Godin: this condition just in order to bypass test
+      if (rec != null) {
+        // SONAR-3072
+
+        List<ViolationPair> possiblePairs = Lists.newArrayList();
+        for (Violation newViolation : newViolations) {
+          for (RuleFailureModel pastViolation : pastViolationsByRule.get(newViolation.getRule().getId())) {
+            int weight = rec.computeLengthOfMaximalBlock(pastViolation.getLine() - 1, newViolation.getLineId() - 1);
+            possiblePairs.add(new ViolationPair(pastViolation, newViolation, weight));
+          }
+        }
+        Collections.sort(possiblePairs, ViolationPair.COMPARATOR);
+
+        Set<RuleFailureModel> pp = Sets.newHashSet(pastViolations);
+        for (ViolationPair pair : possiblePairs) {
+          Violation newViolation = pair.getNewViolation();
+          RuleFailureModel pastViolation = pair.getPastViolation();
+          if (isNotAlreadyMapped(newViolation, referenceViolationsMap) && pp.contains(pastViolation)) {
+            pp.remove(pastViolation);
+            mapViolation(newViolation, pastViolation, pastViolationsByRule, referenceViolationsMap);
+          }
+        }
+
+      }
+
+      // Try then to match violations on same rule with same message and with same checksum
       for (Violation newViolation : newViolations) {
         if (isNotAlreadyMapped(newViolation, referenceViolationsMap)) {
           mapViolation(newViolation,
@@ -128,7 +158,7 @@ public class ViolationTrackingDecorator implements Decorator {
       }
 
       // Last check: match violation if same rule and same checksum but different line and different message
-      // See https://jira.codehaus.org/browse/SONAR-2812
+      // See SONAR-2812
       for (Violation newViolation : newViolations) {
         if (isNotAlreadyMapped(newViolation, referenceViolationsMap)) {
           mapViolation(newViolation,
diff --git a/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest.java b/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest.java
new file mode 100644
index 00000000000..14b6922ca4b
--- /dev/null
+++ b/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest.java
@@ -0,0 +1,49 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2012 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.plugins.core.timemachine;
+
+import org.junit.Test;
+import org.sonar.api.resources.JavaFile;
+import org.sonar.api.resources.Resource;
+import org.sonar.jpa.test.AbstractDbUnitTestCase;
+
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+
+public class ReferenceAnalysisTest extends AbstractDbUnitTestCase {
+
+  @Test
+  public void test() {
+    setupData("shared");
+
+    ReferenceAnalysis referenceAnalysis = new ReferenceAnalysis(getSession());
+
+    Resource resource = new JavaFile("");
+
+    resource.setEffectiveKey("project:org.foo.Bar");
+    assertThat(referenceAnalysis.getViolations(resource).size(), is(1));
+    assertThat(referenceAnalysis.getSource(resource), is("this is the file content"));
+
+    resource.setEffectiveKey("project:no-such-resource");
+    assertThat(referenceAnalysis.getViolations(resource).size(), is(0));
+    assertThat(referenceAnalysis.getSource(resource), is(""));
+  }
+
+}
diff --git a/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizerTest.java b/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizerTest.java
new file mode 100644
index 00000000000..37b5d9db4fb
--- /dev/null
+++ b/plugins/sonar-core-plugin/src/test/java/org/sonar/plugins/core/timemachine/ViolationTrackingBlocksRecognizerTest.java
@@ -0,0 +1,50 @@
+/*
+ * Sonar, open source software quality management tool.
+ * Copyright (C) 2008-2012 SonarSource
+ * mailto:contact AT sonarsource DOT com
+ *
+ * Sonar is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 3 of the License, or (at your option) any later version.
+ *
+ * Sonar is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with Sonar; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02
+ */
+package org.sonar.plugins.core.timemachine;
+
+import org.junit.Test;
+
+import static org.hamcrest.Matchers.is;
+import static org.junit.Assert.assertThat;
+
+public class ViolationTrackingBlocksRecognizerTest {
+
+  @Test
+  public void test() {
+    assertThat(compute(t("abcde"), t("abcde"), 3, 3), is(5));
+    assertThat(compute(t("abcde"), t("abcd"), 3, 3), is(4));
+    assertThat(compute(t("bcde"), t("abcde"), 3, 3), is(0));
+    assertThat(compute(t("bcde"), t("abcde"), 2, 3), is(4));
+  }
+
+  private static int compute(String a, String b, int ai, int bi) {
+    ViolationTrackingBlocksRecognizer rec = new ViolationTrackingBlocksRecognizer(a, b);
+    return rec.computeLengthOfMaximalBlock(ai, bi);
+  }
+
+  private static String t(String text) {
+    StringBuilder sb = new StringBuilder();
+    for (int i = 0; i < text.length(); i++) {
+      sb.append(text.charAt(i)).append('\n');
+    }
+    return sb.toString();
+  }
+
+}
diff --git a/plugins/sonar-core-plugin/src/test/resources/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest/shared.xml b/plugins/sonar-core-plugin/src/test/resources/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest/shared.xml
new file mode 100644
index 00000000000..dd96aeecbf1
--- /dev/null
+++ b/plugins/sonar-core-plugin/src/test/resources/org/sonar/plugins/core/timemachine/ReferenceAnalysisTest/shared.xml
@@ -0,0 +1,16 @@
+<dataset>
+
+  <projects id="200" scope="FIL" qualifier="CLA" kee="project:org.foo.Bar" root_id="[null]"
+            name="Bar" long_name="org.foo.Bar" description="[null]"
+            enabled="true" language="java" copy_resource_id="[null]" person_id="[null]" profile_id="[null]"/>
+
+  <snapshots purge_status="[null]" period1_mode="[null]" period1_param="[null]" period1_date="[null]" period2_mode="[null]" period2_param="[null]" period2_date="[null]" period3_mode="[null]" period3_param="[null]" period3_date="[null]" period4_mode="[null]" period4_param="[null]" period4_date="[null]" period5_mode="[null]" period5_param="[null]" period5_date="[null]" id="1000" project_id="200" parent_snapshot_id="[null]" root_project_id="100" root_snapshot_id="[null]"
+             scope="FIL" qualifier="CLA" created_at="2008-11-01 13:58:00.00" build_date="2008-11-01 13:58:00.00" version="[null]" path=""
+             status="P" islast="true" depth="3" />
+
+  <rule_failures switched_off="false" permanent_id="1" ID="1" SNAPSHOT_ID="1000" RULE_ID="30" FAILURE_LEVEL="3" MESSAGE="old message" LINE="10" COST="[null]"
+                 created_at="2008-11-01 13:58:00.00" checksum="[null]" person_id="[null]"/>
+
+  <snapshot_sources ID="1" SNAPSHOT_ID="1000" DATA="this is the file content"/>
+
+</dataset>