| // Copyright 2019 The Bazel Authors. All rights reserved. |
| // |
| // 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.devtools.build.lib.exec; |
| |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static com.google.common.truth.Truth.assertThat; |
| |
| import com.google.common.collect.ImmutableList; |
| import com.google.devtools.build.lib.exec.Protos.File; |
| import com.google.devtools.build.lib.exec.Protos.SpawnExec; |
| import com.google.devtools.build.lib.util.io.MessageInputStream; |
| import com.google.devtools.build.lib.util.io.MessageInputStreamWrapper.BinaryInputStreamWrapper; |
| import com.google.devtools.build.lib.util.io.MessageOutputStream; |
| import java.io.ByteArrayInputStream; |
| import java.io.ByteArrayOutputStream; |
| import java.io.IOException; |
| import java.util.ArrayList; |
| import java.util.List; |
| import org.junit.Test; |
| import org.junit.runner.RunWith; |
| import org.junit.runners.JUnit4; |
| |
| /** Tests for {@link StableSort}. */ |
| @RunWith(JUnit4.class) |
| public final class StableSortTest { |
| |
| private static class ListOutput implements MessageOutputStream<SpawnExec> { |
| public ArrayList<SpawnExec> list; |
| |
| ListOutput() { |
| list = new ArrayList<>(); |
| } |
| |
| @Override |
| public void write(SpawnExec m) throws IOException { |
| list.add(checkNotNull(m)); |
| } |
| |
| @Override |
| public void close() throws IOException {} |
| } |
| |
| private List<SpawnExec> testStableSort(List<SpawnExec> list) throws Exception { |
| ByteArrayOutputStream baos = new ByteArrayOutputStream(); |
| for (SpawnExec spawn : list) { |
| spawn.writeDelimitedTo(baos); |
| } |
| |
| MessageInputStream<SpawnExec> in = |
| new BinaryInputStreamWrapper<>( |
| new ByteArrayInputStream(baos.toByteArray()), SpawnExec.getDefaultInstance()); |
| |
| ListOutput out = new ListOutput(); |
| |
| StableSort.stableSort(in, out); |
| return out.list; |
| } |
| |
| private static SpawnExec.Builder createSpawnExecBuilder( |
| List<String> inputs, List<String> outputs) { |
| SpawnExec.Builder e = SpawnExec.newBuilder(); |
| for (String output : outputs) { |
| e.addActualOutputsBuilder().setPath(output); |
| e.addListedOutputs(output); |
| } |
| for (String s : inputs) { |
| e.addInputs(File.newBuilder().setPath(s).build()); |
| } |
| return e; |
| } |
| |
| private static SpawnExec createSpawnExec(List<String> inputs, List<String> outputs) { |
| return createSpawnExecBuilder(inputs, outputs).build(); |
| } |
| |
| @Test |
| public void stableSortEmpty() throws Exception { |
| List<SpawnExec> l = testStableSort(ImmutableList.of()); |
| assertThat(l).isEmpty(); |
| } |
| |
| @Test |
| public void stableSortOne() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of(), ImmutableList.of("output")); |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e1)); |
| assertThat(l).containsExactly(e1).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_unlinkedLexicographic() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("a")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("leaf2"), ImmutableList.of("b")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e1, e2)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_unlinkedLexicographic_reverse() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("leaf2"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e1, e2)); |
| assertThat(l).containsExactly(e2, e1).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_linked() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e1, e2)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_linked_inputOrderDoesNotMatter() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e2, e1)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_oneOfMultipleInputs() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b1", "b2", "b3")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("b2"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e2, e1)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_manyOfMultipleInputs() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b1", "b2", "b3")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("b2", "b3"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e2, e1)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_IrrelevantInputs() throws Exception { |
| SpawnExec e1 = createSpawnExec(ImmutableList.of("leaf1"), ImmutableList.of("b1", "b2", "b3")); |
| SpawnExec e2 = createSpawnExec(ImmutableList.of("z", "b2", "1"), ImmutableList.of("a")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(e2, e1)); |
| assertThat(l).containsExactly(e1, e2).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_ABC() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of(""), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of(""), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(a, b, c).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_CBA() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(c, b, a).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_ACB() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of(""), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("a", "c"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(a, c, b).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_CAB() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(c, a, b).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_CAB2() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("c1"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("c2"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c1", "c2")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(c, a, b).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_CBAFED() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| SpawnExec d = createSpawnExec(ImmutableList.of("e"), ImmutableList.of("d")); |
| SpawnExec e = createSpawnExec(ImmutableList.of("f"), ImmutableList.of("e")); |
| SpawnExec f = createSpawnExec(ImmutableList.of(""), ImmutableList.of("f")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c, d, e, f)); |
| assertThat(l).containsExactly(c, b, a, f, e, d).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_InterleavedPaths() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of(""), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of(""), ImmutableList.of("c")); |
| SpawnExec d = createSpawnExec(ImmutableList.of("a"), ImmutableList.of("d")); |
| SpawnExec e = createSpawnExec(ImmutableList.of("f"), ImmutableList.of("e")); |
| SpawnExec f = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("f")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c, d, e, f)); |
| assertThat(l).containsExactly(b, c, a, d, f, e).inOrder(); |
| } |
| |
| @Test |
| public void stableSortTwo_ManyDependencies() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("b", "c", "f"), ImmutableList.of("a")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("d", "e"), ImmutableList.of("b")); |
| SpawnExec c = createSpawnExec(ImmutableList.of("e", "d", "f"), ImmutableList.of("c")); |
| SpawnExec d = createSpawnExec(ImmutableList.of(""), ImmutableList.of("d")); |
| SpawnExec e = createSpawnExec(ImmutableList.of("f"), ImmutableList.of("e")); |
| SpawnExec f = createSpawnExec(ImmutableList.of(""), ImmutableList.of("f")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c, d, e, f)); |
| assertThat(l).containsExactly(d, f, e, b, c, a).inOrder(); |
| } |
| |
| @Test |
| public void stableSort_NoOutputs() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("a"), ImmutableList.of()); |
| SpawnExec b = createSpawnExec(ImmutableList.of("b"), ImmutableList.of()); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b)); |
| assertThat(l).containsExactly(a, b).inOrder(); |
| } |
| |
| @Test |
| public void stableSort_NoOutputs_reversed() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("a"), ImmutableList.of()); |
| SpawnExec b = createSpawnExec(ImmutableList.of("b"), ImmutableList.of()); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(b, a)); |
| assertThat(l).containsExactly(a, b).inOrder(); |
| } |
| |
| @Test |
| public void stableSort_ListedOutputs() throws Exception { |
| |
| SpawnExec a = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("a")) |
| .addCommandArgs("a") |
| .build(); |
| SpawnExec b = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("b").build(); |
| SpawnExec c = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("c")) |
| .addCommandArgs("c") |
| .build(); |
| SpawnExec d = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("d")) |
| .addCommandArgs("d") |
| .build(); |
| SpawnExec e = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("e").build(); |
| SpawnExec f = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("f").build(); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c, d, e, f)); |
| assertThat(l) |
| .containsExactly( |
| // sorted elements with actual outputs |
| a, |
| c, |
| d, |
| // sorted elements without listed outputs |
| b, |
| e, |
| f) |
| .inOrder(); |
| } |
| |
| @Test |
| public void stableSort_ListedOutputs_reordered() throws Exception { |
| SpawnExec a = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("a")) |
| .addCommandArgs("a") |
| .build(); |
| SpawnExec b = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("b").build(); |
| SpawnExec c = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("c")) |
| .addCommandArgs("c") |
| .build(); |
| SpawnExec d = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("d")) |
| .addCommandArgs("d") |
| .build(); |
| SpawnExec e = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("e").build(); |
| SpawnExec f = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("f").build(); |
| |
| // Reordering the input from the previous test does not change the resulting order |
| List<SpawnExec> l = testStableSort(ImmutableList.of(f, e, d, c, b, a)); |
| assertThat(l) |
| .containsExactly( |
| // sorted elements with actual outputs |
| a, |
| c, |
| d, |
| // sorted elements without listed outputs |
| b, |
| e, |
| f) |
| .inOrder(); |
| } |
| |
| @Test |
| public void stableSort_ListedOutputs_dependencies() throws Exception { |
| // Dependencies are respected |
| SpawnExec a = |
| createSpawnExecBuilder(ImmutableList.of("d"), ImmutableList.of("a")) |
| .addCommandArgs("a") |
| .build(); |
| SpawnExec b = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("b").build(); |
| SpawnExec c = |
| createSpawnExecBuilder(ImmutableList.of("d"), ImmutableList.of("c")) |
| .addCommandArgs("c") |
| .build(); |
| SpawnExec d = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of("d")) |
| .addCommandArgs("d") |
| .build(); |
| SpawnExec e = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("e").build(); |
| SpawnExec f = |
| createSpawnExecBuilder(ImmutableList.of(), ImmutableList.of()).addCommandArgs("f").build(); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(f, e, d, c, b, a)); |
| assertThat(l).containsExactly(d, a, c, b, e, f).inOrder(); |
| } |
| |
| @Test |
| public void stableSort_execsWithDuplicateOutputs() throws Exception { |
| SpawnExec a = createSpawnExec(ImmutableList.of("a"), ImmutableList.of("c")); |
| SpawnExec b = createSpawnExec(ImmutableList.of("b"), ImmutableList.of("c")); |
| SpawnExec c = createSpawnExec(ImmutableList.of("c"), ImmutableList.of("d")); |
| |
| List<SpawnExec> l = testStableSort(ImmutableList.of(a, b, c)); |
| assertThat(l).containsExactly(a, b, c).inOrder(); |
| } |
| } |