IN claus and group of OR should have constant order and no duplicate

2 files changed, 115 insertions, 5 deletions

diff --git a/sonar-db/src/main/java/org/sonar/db/DatabaseUtils.java b/sonar-db/src/main/java/org/sonar/db/DatabaseUtils.java
index 7f45c22125d..5977fd73642 100644
--- a/sonar-db/src/main/java/org/sonar/db/DatabaseUtils.java
+++ b/sonar-db/src/main/java/org/sonar/db/DatabaseUtils.java
@@ -20,7 +20,10 @@
 package org.sonar.db;
 
 import com.google.common.base.Function;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
+import com.google.common.collect.Sets;
 import java.sql.Connection;
 import java.sql.ResultSet;
 import java.sql.SQLException;
@@ -31,6 +34,7 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.Date;
 import java.util.List;
+import java.util.Set;
 import javax.annotation.CheckForNull;
 import javax.annotation.Nullable;
 import org.sonar.api.utils.log.Logger;
@@ -117,20 +121,42 @@ public class DatabaseUtils {
    * The goal is to prevent issue with ORACLE when there's more than 1000 elements in a 'in ('X', 'Y', ...)'
    * and with MsSQL when there's more than 2000 parameters in a query
    */
-  public static <OUTPUT, INPUT> List<OUTPUT> executeLargeInputs(Collection<INPUT> input, Function<List<INPUT>, List<OUTPUT>> function) {
+  public static <OUTPUT, INPUT extends Comparable<INPUT>> List<OUTPUT> executeLargeInputs(Collection<INPUT> input, Function<List<INPUT>, List<OUTPUT>> function) {
     if (input.isEmpty()) {
       return Collections.emptyList();
     }
     List<OUTPUT> results = new ArrayList<>(input.size());
-    List<List<INPUT>> partitionList = Lists.partition(newArrayList(input), PARTITION_SIZE_FOR_ORACLE);
-    for (List<INPUT> partition : partitionList) {
+    for (List<INPUT> partition : toUniqueAndSortedPartitions(input)) {
       List<OUTPUT> subResults = function.apply(partition);
-      results.addAll(subResults);
+      if (subResults != null) {
+        results.addAll(subResults);
+      }
     }
     return results;
   }
 
   /**
+   * Ensure values {@code inputs} are unique (which avoids useless arguments) and sorted before creating the partition.
+   */
+  private static <INPUT extends Comparable<INPUT>> Iterable<List<INPUT>> toUniqueAndSortedPartitions(Collection<INPUT> inputs) {
+    return Iterables.partition(toUniqueAndSortedList(inputs), PARTITION_SIZE_FOR_ORACLE);
+  }
+
+  /**
+   * Ensure values {@code inputs} are unique (which avoids useless arguments) and sorted so that there is little
+   * variations of SQL requests over time as possible with a IN clause and/or a group of OR clauses. Such requests can
+   * then be more easily optimized by the SGDB engine.
+   */
+  public static <INPUT extends Comparable<INPUT>> List<INPUT> toUniqueAndSortedList(Iterable<INPUT> inputs) {
+    if (inputs instanceof Set) {
+      // inputs are unique but order is not enforced
+      return Ordering.natural().immutableSortedCopy(inputs);
+    }
+    // inputs are not unique and order is not guaranteed
+    return Ordering.natural().immutableSortedCopy(Sets.newHashSet(inputs));
+  }
+
+  /**
    * Partition by 1000 elements a list of input and execute a function on each part.
    * The function has not output (ex: delete operation)
    *
diff --git a/sonar-db/src/test/java/org/sonar/db/DatabaseUtilsTest.java b/sonar-db/src/test/java/org/sonar/db/DatabaseUtilsTest.java
index e6097677629..31c928808f1 100644
--- a/sonar-db/src/test/java/org/sonar/db/DatabaseUtilsTest.java
+++ b/sonar-db/src/test/java/org/sonar/db/DatabaseUtilsTest.java
@@ -27,10 +27,14 @@ import java.sql.ResultSet;
 import java.sql.SQLException;
 import java.sql.Statement;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.List;
+import java.util.Objects;
+import javax.annotation.Nullable;
 import org.junit.Rule;
 import org.junit.Test;
 import org.junit.experimental.categories.Category;
+import org.junit.rules.ExpectedException;
 import org.sonar.api.utils.System2;
 import org.sonar.api.utils.log.LogTester;
 import org.sonar.api.utils.log.LoggerLevel;
@@ -39,12 +43,14 @@ import org.sonar.db.dialect.Oracle;
 import org.sonar.test.DbTests;
 
 import static com.google.common.collect.Lists.newArrayList;
+import static java.util.Arrays.asList;
 import static org.assertj.core.api.Assertions.assertThat;
 import static org.assertj.core.api.Assertions.fail;
 import static org.mockito.Mockito.doThrow;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.verify;
 import static org.sonar.db.DatabaseUtils.buildLikeValue;
+import static org.sonar.db.DatabaseUtils.toUniqueAndSortedList;
 import static org.sonar.db.WildcardPosition.AFTER;
 import static org.sonar.db.WildcardPosition.BEFORE;
 import static org.sonar.db.WildcardPosition.BEFORE_AND_AFTER;
@@ -54,7 +60,8 @@ public class DatabaseUtilsTest {
 
   @Rule
   public DbTester dbTester = DbTester.create(System2.INSTANCE);
-
+  @Rule
+  public ExpectedException expectedException = ExpectedException.none();
   @Rule
   public LogTester logTester = new LogTester();
 
@@ -123,6 +130,83 @@ public class DatabaseUtilsTest {
     verify(rs).close(); // just to be sure
   }
 
+  @Test
+  public void toUniqueAndSortedList_throws_NPE_if_arg_is_null() {
+    expectedException.expect(NullPointerException.class);
+
+    toUniqueAndSortedList(null);
+  }
+
+  @Test
+  public void toUniqueAndSortedList_throws_NPE_if_arg_contains_a_null() {
+    expectedException.expect(NullPointerException.class);
+
+    toUniqueAndSortedList(asList("A", null, "C"));
+  }
+
+  @Test
+  public void toUniqueAndSortedList_throws_NPE_if_arg_is_a_set_containing_a_null() {
+    expectedException.expect(NullPointerException.class);
+
+    toUniqueAndSortedList(new HashSet<Comparable>(asList("A", null, "C")));
+  }
+
+  @Test
+  public void toUniqueAndSortedList_enforces_natural_order() {
+    assertThat(toUniqueAndSortedList(asList("A", "B", "C"))).containsExactly("A", "B", "C");
+    assertThat(toUniqueAndSortedList(asList("B", "A", "C"))).containsExactly("A", "B", "C");
+    assertThat(toUniqueAndSortedList(asList("B", "C", "A"))).containsExactly("A", "B", "C");
+  }
+
+  @Test
+  public void toUniqueAndSortedList_removes_duplicates() {
+    assertThat(toUniqueAndSortedList(asList("A", "A", "A"))).containsExactly("A");
+    assertThat(toUniqueAndSortedList(asList("A", "C", "A"))).containsExactly("A", "C");
+    assertThat(toUniqueAndSortedList(asList("C", "C", "B", "B", "A", "N", "C", "A"))).containsExactly("A", "B", "C", "N");
+  }
+
+  @Test
+  public void toUniqueAndSortedList_removes_duplicates_and_apply_natural_order_of_any_Comparable() {
+    assertThat(
+      toUniqueAndSortedList(asList(myComparable(2), myComparable(5), myComparable(2), myComparable(4), myComparable(-1), myComparable(10))))
+      .containsExactly(
+        myComparable(-1), myComparable(2), myComparable(4), myComparable(5), myComparable(10));
+  }
+
+  private static DatabaseUtilsTest.MyComparable myComparable(int ordinal) {
+    return new DatabaseUtilsTest.MyComparable(ordinal);
+  }
+
+  private static final class MyComparable implements Comparable<MyComparable> {
+    private final int ordinal;
+
+    private MyComparable(int ordinal) {
+      this.ordinal = ordinal;
+    }
+
+    @Override
+    public int compareTo(MyComparable o) {
+      return ordinal - o.ordinal;
+    }
+
+    @Override
+    public boolean equals(@Nullable Object o) {
+      if (this == o) {
+        return true;
+      }
+      if (o == null || getClass() != o.getClass()) {
+        return false;
+      }
+      MyComparable that = (MyComparable) o;
+      return ordinal == that.ordinal;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(ordinal);
+    }
+  }
+
   /**
    * Connection.isClosed() has been introduced in java 1.6
    */