src/test/java/com/google/devtools/build/lib/skyframe/SkyframeFocuserTest.java

// Copyright 2023 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.skyframe;

import static com.google.common.truth.Truth.assertThat;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.analysis.util.BuildViewTestCase;
import com.google.devtools.build.lib.skyframe.SkyframeFocuser.FocusResult;
import com.google.devtools.build.skyframe.AbstractSkyKey;
import com.google.devtools.build.skyframe.GraphTester.StringValue;
import com.google.devtools.build.skyframe.InMemoryGraph;
import com.google.devtools.build.skyframe.NodeEntry;
import com.google.devtools.build.skyframe.QueryableGraph.Reason;
import com.google.devtools.build.skyframe.SkyFunctionName;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.Version;
import java.util.Set;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/** Tests for {@link SkyframeFocuser}. */
@RunWith(JUnit4.class)
public final class SkyframeFocuserTest extends BuildViewTestCase {

  @Test
  public void testFocus_emptyInputsReturnsEmptyResult() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    FocusResult focusResult =
        SkyframeFocuser.focus(graph, reporter, Sets.newHashSet(), Sets.newHashSet());

    assertThat(focusResult.getDeps()).isEmpty();
    assertThat(focusResult.getRdeps()).isEmpty();
  }

  @Test
  public void testFocus_keepsLeafs() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog);

    graph.createIfAbsentBatch(null, Reason.OTHER, keys);

    createEdgesAndMarkDone(graph, cat, ImmutableList.of(), ImmutableList.of());
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet();
    Set<SkyKey> leafs = Sets.newHashSet(cat, dog);

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).isEmpty();
    assertThat(focusResult.getRdeps()).containsExactly(cat, dog);
    assertThat(graph.getValues().keySet()).containsExactly(cat, dog);
  }

  @Test
  public void testFocus_dropsUnreachableNodesFromLeafs() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog);

    graph.createIfAbsentBatch(null, Reason.OTHER, keys);

    createEdgesAndMarkDone(graph, cat, ImmutableList.of(), ImmutableList.of());
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet();
    Set<SkyKey> leafs = Sets.newHashSet(cat); // dog is unreachable

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).isEmpty();
    assertThat(focusResult.getRdeps()).containsExactly(cat);
    assertThat(graph.getValues().keySet()).containsExactly(cat);
  }

  @Test
  public void testFocus_keepsReverseDepOfLeafs() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog);

    graph.createIfAbsentBatch(null, Reason.OTHER, keys);
    createEdgesAndMarkDone(graph, cat, ImmutableList.of(), ImmutableList.of(dog));
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet();
    Set<SkyKey> leafs = Sets.newHashSet(cat); // dog is cat's rdep

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).isEmpty();
    assertThat(focusResult.getRdeps()).containsExactly(cat, dog);
    assertThat(graph.getValues().keySet()).containsExactly(cat, dog);
  }

  @Test
  public void testFocus_keepsRoots() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog);

    graph.createIfAbsentBatch(null, Reason.OTHER, keys);
    createEdgesAndMarkDone(graph, cat, ImmutableList.of(), ImmutableList.of());
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet(cat, dog);
    Set<SkyKey> leafs = Sets.newHashSet();

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).containsExactly(cat, dog);
    assertThat(focusResult.getRdeps()).isEmpty();
    assertThat(graph.getValues().keySet()).containsExactly(cat, dog);
  }

  @Test
  public void testFocus_dropsUnreachableFromRoots() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog);

    graph.createIfAbsentBatch(null, Reason.OTHER, keys);
    createEdgesAndMarkDone(graph, cat, ImmutableList.of(), ImmutableList.of());
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet(cat);
    Set<SkyKey> leafs = Sets.newHashSet();

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).containsExactly(cat);
    assertThat(focusResult.getRdeps()).isEmpty();
    assertThat(graph.getValues().keySet()).containsExactly(cat);
  }

  @Test
  public void testFocus_keepDirectDepsOfRdepTransitiveClosure() throws InterruptedException {
    InMemoryGraph graph = skyframeExecutor.getEvaluator().getInMemoryGraph();
    SkyKey cat = SkyKeyWithSkyKeyInterner.create("cat");
    SkyKey dog = SkyKeyWithSkyKeyInterner.create("dog");
    SkyKey civet = SkyKeyWithSkyKeyInterner.create("civet");
    SkyKey hamster = SkyKeyWithSkyKeyInterner.create("hamster");
    SkyKey fish = SkyKeyWithSkyKeyInterner.create("fish");
    SkyKey bird = SkyKeyWithSkyKeyInterner.create("bird");
    SkyKey monkey = SkyKeyWithSkyKeyInterner.create("monkey");
    ImmutableList<SkyKey> keys = ImmutableList.of(cat, dog, civet, hamster, fish, bird, monkey);
    graph.createIfAbsentBatch(null, Reason.OTHER, keys);

    // Graph:
    //
    // monkey (isolated)
    //
    //    /-> fish -> bird
    // cat -> dog -> civet*
    //          \-> hamster
    //
    // *Only civet in the working set.
    createEdgesAndMarkDone(graph, civet, ImmutableList.of(), ImmutableList.of(dog));
    createEdgesAndMarkDone(graph, hamster, ImmutableList.of(), ImmutableList.of(dog));
    createEdgesAndMarkDone(graph, dog, ImmutableList.of(civet, hamster), ImmutableList.of(cat));
    createEdgesAndMarkDone(graph, bird, ImmutableList.of(), ImmutableList.of(fish));
    createEdgesAndMarkDone(graph, fish, ImmutableList.of(bird), ImmutableList.of(cat));
    createEdgesAndMarkDone(graph, cat, ImmutableList.of(dog, fish), ImmutableList.of());

    Set<SkyKey> roots = Sets.newHashSet(cat);
    Set<SkyKey> leafs = Sets.newHashSet(civet);

    FocusResult focusResult = SkyframeFocuser.focus(graph, reporter, roots, leafs);

    assertThat(focusResult.getDeps()).containsExactly(hamster, fish);
    assertThat(focusResult.getRdeps()).containsExactly(civet, dog, cat);

    // no monkey (isolated) and bird (indirect dep)
    assertThat(graph.getValues().keySet()).containsExactly(hamster, fish, civet, dog, cat);
  }

  // Create dep and rdep edges for a node, and ensures that it's marked done.
  private static void createEdgesAndMarkDone(
      InMemoryGraph graph, SkyKey k, ImmutableList<SkyKey> deps, ImmutableList<SkyKey> rdeps)
      throws InterruptedException {
    NodeEntry entry = graph.getIfPresent(k);
    assertThat(entry).isNotNull();
    if (rdeps.isEmpty()) {
      entry.addReverseDepAndCheckIfDone(null);
    } else {
      for (SkyKey rdep : rdeps) {
        entry.addReverseDepAndCheckIfDone(rdep);
      }
    }
    entry.markRebuilding();
    for (SkyKey dep : deps) {
      entry.addSingletonTemporaryDirectDep(dep);
      entry.signalDep(Version.constant(), dep);
    }
    entry.setValue(new StringValue("unused"), Version.constant(), null);
  }

  private static final class SkyKeyWithSkyKeyInterner extends AbstractSkyKey<String> {
    private static final SkyKeyInterner<SkyframeFocuserTest.SkyKeyWithSkyKeyInterner> interner =
        SkyKey.newInterner();

    static SkyKeyWithSkyKeyInterner create(String arg) {
      return interner.intern(new SkyframeFocuserTest.SkyKeyWithSkyKeyInterner(arg));
    }

    private SkyKeyWithSkyKeyInterner(String arg) {
      super(arg);
    }

    @Override
    public SkyFunctionName functionName() {
      return SkyFunctionName.FOR_TESTING;
    }

    @Override
    public SkyKeyInterner<SkyframeFocuserTest.SkyKeyWithSkyKeyInterner> getSkyKeyInterner() {
      return interner;
    }
  }
}