path: root/javatests/com/google/gerrit/server/notedb/rebuild/EventSorterTest.java

// Copyright (C) 2016 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package com.google.gerrit.server.notedb.rebuild;

import static com.google.common.truth.Truth.assertThat;
import static java.util.stream.Collectors.toList;
import static org.junit.Assert.fail;

import com.google.common.collect.Collections2;
import com.google.common.collect.Lists;
import com.google.gerrit.reviewdb.client.Account;
import com.google.gerrit.reviewdb.client.Change;
import com.google.gerrit.reviewdb.client.PatchSet;
import com.google.gerrit.server.notedb.ChangeUpdate;
import com.google.gerrit.server.util.time.TimeUtil;
import com.google.gerrit.testing.TestTimeUtil;
import java.sql.Timestamp;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.stream.Stream;
import org.junit.Before;
import org.junit.Test;

public class EventSorterTest {
  private class TestEvent extends Event {
    protected TestEvent(Timestamp when) {
      super(
          new PatchSet.Id(new Change.Id(1), 1),
          new Account.Id(1000),
          new Account.Id(1000),
          when,
          changeCreatedOn,
          null);
    }

    @Override
    boolean uniquePerUpdate() {
      return false;
    }

    @Override
    void apply(ChangeUpdate update) {
      throw new UnsupportedOperationException();
    }

    @SuppressWarnings("deprecation")
    @Override
    public String toString() {
      return "E{" + when.getSeconds() + '}';
    }
  }

  private Timestamp changeCreatedOn;

  @Before
  public void setUp() {
    TestTimeUtil.resetWithClockStep(10, TimeUnit.SECONDS);
    changeCreatedOn = TimeUtil.nowTs();
  }

  @Test
  public void naturalSort() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());
    Event e3 = new TestEvent(TimeUtil.nowTs());

    for (List<Event> events : Collections2.permutations(events(e1, e2, e3))) {
      assertSorted(events, events(e1, e2, e3));
    }
  }

  @Test
  public void topoSortOneDep() {
    List<Event> es;

    // Input list is 0,1,2

    // 0 depends on 1 => 1,0,2
    es = threeEventsOneDep(0, 1);
    assertSorted(es, events(es, 1, 0, 2));

    // 1 depends on 0 => 0,1,2
    es = threeEventsOneDep(1, 0);
    assertSorted(es, events(es, 0, 1, 2));

    // 0 depends on 2 => 1,2,0
    es = threeEventsOneDep(0, 2);
    assertSorted(es, events(es, 1, 2, 0));

    // 2 depends on 0 => 0,1,2
    es = threeEventsOneDep(2, 0);
    assertSorted(es, events(es, 0, 1, 2));

    // 1 depends on 2 => 0,2,1
    es = threeEventsOneDep(1, 2);
    assertSorted(es, events(es, 0, 2, 1));

    // 2 depends on 1 => 0,1,2
    es = threeEventsOneDep(2, 1);
    assertSorted(es, events(es, 0, 1, 2));
  }

  private List<Event> threeEventsOneDep(int depFromIdx, int depOnIdx) {
    List<Event> events =
        Lists.newArrayList(
            new TestEvent(TimeUtil.nowTs()),
            new TestEvent(TimeUtil.nowTs()),
            new TestEvent(TimeUtil.nowTs()));
    events.get(depFromIdx).addDep(events.get(depOnIdx));
    return events;
  }

  @Test
  public void lastEventDependsOnFirstEvent() {
    List<Event> events = new ArrayList<>();
    for (int i = 0; i < 20; i++) {
      events.add(new TestEvent(TimeUtil.nowTs()));
    }
    events.get(events.size() - 1).addDep(events.get(0));
    assertSorted(events, events);
  }

  @Test
  public void firstEventDependsOnLastEvent() {
    List<Event> events = new ArrayList<>();
    for (int i = 0; i < 20; i++) {
      events.add(new TestEvent(TimeUtil.nowTs()));
    }
    events.get(0).addDep(events.get(events.size() - 1));

    List<Event> expected = new ArrayList<>();
    expected.addAll(events.subList(1, events.size()));
    expected.add(events.get(0));
    assertSorted(events, expected);
  }

  @Test
  public void topoSortChainOfDeps() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());
    Event e3 = new TestEvent(TimeUtil.nowTs());
    Event e4 = new TestEvent(TimeUtil.nowTs());
    e1.addDep(e2);
    e2.addDep(e3);
    e3.addDep(e4);

    assertSorted(events(e1, e2, e3, e4), events(e4, e3, e2, e1));
  }

  @Test
  public void topoSortMultipleDeps() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());
    Event e3 = new TestEvent(TimeUtil.nowTs());
    Event e4 = new TestEvent(TimeUtil.nowTs());
    e1.addDep(e2);
    e1.addDep(e4);
    e2.addDep(e3);

    // Processing 3 pops 2, processing 4 pops 1.
    assertSorted(events(e2, e3, e1, e4), events(e3, e2, e4, e1));
  }

  @Test
  public void topoSortMultipleDepsPreservesNaturalOrder() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());
    Event e3 = new TestEvent(TimeUtil.nowTs());
    Event e4 = new TestEvent(TimeUtil.nowTs());
    e1.addDep(e4);
    e2.addDep(e4);
    e3.addDep(e4);

    // Processing 4 pops 1, 2, 3 in natural order.
    assertSorted(events(e4, e3, e2, e1), events(e4, e1, e2, e3));
  }

  @Test
  public void topoSortCycle() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());

    // Implementation is not really defined, but infinite looping would be bad.
    // According to current implementation details, 2 pops 1, 1 pops 2 which was
    // already seen.
    assertSorted(events(e2, e1), events(e1, e2));
  }

  @Test
  public void topoSortDepNotInInputList() {
    Event e1 = new TestEvent(TimeUtil.nowTs());
    Event e2 = new TestEvent(TimeUtil.nowTs());
    Event e3 = new TestEvent(TimeUtil.nowTs());
    e1.addDep(e3);

    List<Event> events = events(e2, e1);
    try {
      new EventSorter(events).sort();
      fail("expected IllegalArgumentException");
    } catch (IllegalArgumentException e) {
      // Expected.
    }
  }

  private static List<Event> events(Event... es) {
    return Lists.newArrayList(es);
  }

  private static List<Event> events(List<Event> in, Integer... indexes) {
    return Stream.of(indexes).map(in::get).collect(toList());
  }

  private static void assertSorted(List<Event> unsorted, List<Event> expected) {
    List<Event> actual = new ArrayList<>(unsorted);
    new EventSorter(actual).sort();
    assertThat(actual).named("sorted" + unsorted).isEqualTo(expected);
  }
}