src/main/java/com/google/devtools/build/lib/query2/FilteredDirectRdepsInUniverseExpressionMapper.java

// 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.query2;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.devtools.build.lib.cmdline.TargetPattern;
import com.google.devtools.build.lib.query2.engine.BinaryOperatorExpression;
import com.google.devtools.build.lib.query2.engine.FunctionExpression;
import com.google.devtools.build.lib.query2.engine.LetExpression;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.FilteringQueryFunction;
import com.google.devtools.build.lib.query2.engine.QueryExpression;
import com.google.devtools.build.lib.query2.engine.QueryExpressionMapper;
import com.google.devtools.build.lib.query2.engine.QueryExpressionVisitor;
import com.google.devtools.build.lib.query2.engine.RdepsFunction;
import com.google.devtools.build.lib.query2.engine.SetExpression;
import com.google.devtools.build.lib.query2.engine.TargetLiteral;
import java.util.ArrayList;
import java.util.List;

/**
 * A {@link QueryExpressionMapper} that transforms each occurrence of an expression of the form
 * {@literal 'rdeps(filterfunc(<pat>, <universeScope>), <T>, 1)'} to {@literal 'filterfunc(<pat>,
 * rdeps(<universeScope>, <T>, 1))'}.
 *
 * <p>By factoring the filterfunc out of the rdeps universe, we prepare the query for transformation
 * by the {@link RdepsToAllRdepsQueryExpressionMapper}.
 *
 * <p><em>Note:</em> we require a max depth of 1 because the transformation is only sound with a
 * depth of 1. Consider a query of depth 2.
 *
 * <ol>
 *   <li>{@literal 'rdeps(kind(^foo$, //...), //base:b, 2)'} yields these two disjoint sets:
 *       <ol>
 *         <li>targets of kind 'foo' that depend directly on //base:b
 *         <li>targets of kind 'foo' that do not depend directly on //base:b, and depend on a target
 *             of kind 'foo' that itself depends directly on //base:b
 *       </ol>
 *   <li>{@literal 'kind(^foo$, rdeps(//..., //base:b, 2))'} yields these two disjoint sets:
 *       <ol>
 *         <li>targets of kind 'foo' that depend directly on //base:b
 *         <li>targets of kind 'foo' that do not depend directly on //base:b, and depend on a target
 *             of <em>any</em> kind that itself depends directly on //base:b
 *       </ol>
 * </ol>
 *
 * With a depth of 1, the rdeps operator in both queries would return only the first set: proof the
 * transformation is sound. With a depth of 2, we see the rdeps operator with a filtered universe
 * returns a strictly smaller set.
 */
public class FilteredDirectRdepsInUniverseExpressionMapper extends QueryExpressionMapper<Void> {
  private final TargetPattern.Parser targetPatternParser;
  private final String absoluteUniverseScopePattern;

  @VisibleForTesting
  public FilteredDirectRdepsInUniverseExpressionMapper(
      TargetPattern.Parser targetPatternParser, String universeScopePattern) {
    this.targetPatternParser = targetPatternParser;
    this.absoluteUniverseScopePattern = targetPatternParser.absolutize(universeScopePattern);
  }

  @Override
  public QueryExpression visit(FunctionExpression functionExpression, Void context) {
    if (functionExpression.getFunction().getName().equals(new RdepsFunction().getName())) {
      List<Argument> args = functionExpression.getArgs();
      // This transformation only applies to the 3-arg form of rdeps, with depth == 1.
      if (args.size() == 3 && args.get(2).getInteger() == 1) {
        List<FunctionExpression> universeFilteringFunctions =
            args.get(0).getExpression().accept(new ExtractFilteringFunctionsFromUniverseVisitor());
        // If we get back a non-empty list of FunctionExpressions, these are filtering functions
        // that can be safely factored out.
        if (!universeFilteringFunctions.isEmpty()) {
          QueryExpression curFunction = makeUnfilteredRdepsWithDepthOne(args.get(1));
          for (FunctionExpression filterExpr : universeFilteringFunctions) {
            curFunction = wrapExprWithFilter(curFunction, filterExpr);
          }
          return curFunction;
        }
      }
    }
    return super.visit(functionExpression, context);
  }

  private FunctionExpression makeUnfilteredRdepsWithDepthOne(Argument target) {
    return new FunctionExpression(
        new RdepsFunction(),
        ImmutableList.of(
            Argument.of(new TargetLiteral(absoluteUniverseScopePattern)), target, Argument.of(1)));
  }

  private static QueryExpression wrapExprWithFilter(
      QueryExpression curFunction, FunctionExpression filterExpr) {
    List<Argument> filterExprArgs = filterExpr.getArgs();
    FilteringQueryFunction filteringFunction = filterExpr.getFunction().asFilteringFunction();
    List<Argument> rewrittenArgs = new ArrayList<>();
    for (int i = 0; i < filterExprArgs.size(); i++) {
      if (i == filteringFunction.getExpressionToFilterIndex()) {
        rewrittenArgs.add(Argument.of(curFunction));
      } else {
        rewrittenArgs.add(filterExprArgs.get(i));
      }
    }
    return new FunctionExpression(filteringFunction, rewrittenArgs);
  }

  /**
   * Internal visitor applied to the universe argument of all QueryExpressions of the form {@literal
   * rdeps(u, x, 1)}.
   */
  private class ExtractFilteringFunctionsFromUniverseVisitor
      implements QueryExpressionVisitor<List<FunctionExpression>, Void> {

    @Override
    public List<FunctionExpression> visit(TargetLiteral targetLiteral, Void context) {
      return ImmutableList.of();
    }

    @Override
    public List<FunctionExpression> visit(
        BinaryOperatorExpression binaryOperatorExpression, Void context) {
      return ImmutableList.of();
    }

    @SuppressWarnings("MixedMutabilityReturnType")
    @Override
    public List<FunctionExpression> visit(FunctionExpression functionExpression, Void context) {
      FilteringQueryFunction filteringFunction =
          functionExpression.getFunction().asFilteringFunction();
      if (filteringFunction == null) {
        return ImmutableList.of();
      }
      Argument filteredArgument =
          functionExpression.getArgs().get(filteringFunction.getExpressionToFilterIndex());
      Preconditions.checkArgument(filteredArgument.getType() == ArgumentType.EXPRESSION);
      QueryExpression filteredExpression = filteredArgument.getExpression();

      ArrayList<FunctionExpression> results = new ArrayList<>();
      if (filteredExpression instanceof TargetLiteral) {
        TargetLiteral literalUniverseExpression = (TargetLiteral) filteredExpression;
        String absolutizedUniverseExpression =
            targetPatternParser.absolutize(literalUniverseExpression.getPattern());
        if (absolutizedUniverseExpression.equals(absoluteUniverseScopePattern)) {
          results.add(functionExpression);
        }
      } else if (filteredExpression instanceof FunctionExpression) {
        List<FunctionExpression> nestedFilters = filteredExpression.accept(this);
        if (!nestedFilters.isEmpty()) {
          results.addAll(nestedFilters);
          results.add(functionExpression);
        }
      }
      return results;
    }

    @Override
    public List<FunctionExpression> visit(LetExpression letExpression, Void context) {
      return ImmutableList.of();
    }

    @Override
    public List<FunctionExpression> visit(SetExpression setExpression, Void context) {
      return ImmutableList.of();
    }
  }
}