// 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.packages.producers;

import static com.google.common.collect.ImmutableSet.toImmutableSet;

import com.google.auto.value.AutoValue;
import com.google.common.base.Preconditions;
import com.google.common.base.Splitter;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.cmdline.RepositoryName;
import com.google.devtools.build.lib.packages.Globber;
import com.google.devtools.build.lib.skyframe.GlobDescriptor;
import com.google.devtools.build.lib.skyframe.IgnoredPackagePrefixesValue;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.Root;
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.state.StateMachine;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Consumer;
import java.util.regex.Pattern;
import javax.annotation.Nullable;

/**
 * Serves as the entrance {@link StateMachine} to compute a single glob. There are two ways to
 * create {@link GlobComputationProducer}:
 *
 * <ul>
 *   <li>When each glob within a package is represented as an individual GLOB node, {@link
 *       com.google.devtools.build.lib.skyframe.GlobFunctionWithRecursionInSingleFunction} creates
 *       {@link GlobComputationProducer} to start the computation of each GLOB node.
 *   <li>Glob computations within in a package are aggregated into a single GLOBS node. {@link
 *       com.google.devtools.build.lib.skyframe.GlobsFunction} creates {@link GlobsProducer}, which
 *       further creates {@link GlobComputationProducer} to compute each glob.
 * </ul>
 *
 * <p>Ignored package prefix (IPP) patterns can be optionally passed in. {@link
 * GlobComputationProducer} will query the IPP patterns in Skyframe if not provided. Then it starts
 * the {@link FragmentProducer}s chain which recursively process each glob pattern fragment. Accepts
 * and aggregates globbing matching {@link PathFragment}s result.
 */
public class GlobComputationProducer
    implements StateMachine, Consumer<SkyValue>, FragmentProducer.ResultSink {

  /**
   * Propagates all glob matching {@link PathFragment}s or any {@link Exception}.
   *
   * <p>If any {@link GlobError} is accepted, the already discovered path fragments are still
   * reported. However, {@link com.google.devtools.build.lib.skyframe.GlobFunction} and {@link
   * com.google.devtools.build.lib.skyframe.GlobsFunction} throw the first discovered {@link
   * GlobError} wrapped in a {@link com.google.devtools.build.lib.skyframe.GlobException}.
   *
   * <p>The already discovered path fragments should be considered as undefined. Since: (1) there is
   * no skyframe restart after glob computation throws an exception, so the discovered path
   * fragments can miss some matchings; (2) these discovered path fragments are not used to
   * construct a {@link com.google.devtools.build.lib.skyframe.GlobValue} or {@link
   * com.google.devtools.build.lib.skyframe.GlobsValue}.
   */
  public interface ResultSink {
    void acceptPathFragmentsWithoutPackageFragment(ImmutableSet<PathFragment> pathFragments);

    void acceptGlobError(GlobError error);
  }

  // -------------------- Input --------------------
  private final GlobDescriptor globDescriptor;
  private final ResultSink resultSink;

  // -------------------- Internal State --------------------
  private final ImmutableSet.Builder<PathFragment> pathFragmentsWithPackageFragment;
  private ImmutableSet<PathFragment> ignoredPackagePrefixPatterns;
  private final ConcurrentHashMap<String, Pattern> regexPatternCache;

  public GlobComputationProducer(
      GlobDescriptor globDescriptor,
      @Nullable ImmutableSet<PathFragment> ignoredPackagePrefixPatterns,
      ConcurrentHashMap<String, Pattern> regexPatternCache,
      ResultSink resultSink) {
    this.globDescriptor = globDescriptor;
    this.ignoredPackagePrefixPatterns = ignoredPackagePrefixPatterns;
    this.regexPatternCache = regexPatternCache;
    this.resultSink = resultSink;
    this.pathFragmentsWithPackageFragment = ImmutableSet.builder();
  }

  @Override
  public StateMachine step(Tasks tasks) throws InterruptedException {
    if (ignoredPackagePrefixPatterns == null) {
      // Query ignorePatterPrefixPatterns in Skyframe if not provided.
      RepositoryName repositoryName = globDescriptor.getPackageId().getRepository();
      tasks.lookUp(IgnoredPackagePrefixesValue.key(repositoryName), (Consumer<SkyValue>) this);
    }
    return this::createFragmentProducer;
  }

  @Override
  public void accept(SkyValue skyValue) {
    this.ignoredPackagePrefixPatterns = ((IgnoredPackagePrefixesValue) skyValue).getPatterns();
  }

  private StateMachine createFragmentProducer(Tasks tasks) {
    Preconditions.checkNotNull(ignoredPackagePrefixPatterns);
    ImmutableList<String> patterns =
        ImmutableList.copyOf(Splitter.on('/').split(globDescriptor.getPattern()));
    GlobDetail globDetail =
        GlobDetail.create(
            globDescriptor.getPackageId(),
            globDescriptor.getPackageRoot(),
            patterns,
            /* containsMultipleDoubleStars= */ Collections.frequency(patterns, "**") > 1,
            ignoredPackagePrefixPatterns,
            regexPatternCache,
            globDescriptor.globberOperation());
    Set<Pair<PathFragment, Integer>> visitedGlobSubTasks = null;
    if (globDetail.containsMultipleDoubleStars()) {
      visitedGlobSubTasks = new HashSet<>();
    }
    tasks.enqueue(
        new FragmentProducer(
            globDetail,
            globDetail
                .packageIdentifier()
                .getPackageFragment()
                .getRelative(globDescriptor.getSubdir()),
            /* fragmentIndex= */ 0,
            visitedGlobSubTasks,
            (FragmentProducer.ResultSink) this));
    return this::buildAndBubbleUpResult;
  }

  @Override
  public void acceptPathFragmentWithPackageFragment(PathFragment pathFragment) {
    pathFragmentsWithPackageFragment.add(pathFragment);
  }

  @Override
  public void acceptGlobError(GlobError error) {
    resultSink.acceptGlobError(error);
  }

  /**
   * Removes the package fragment from all accepted matching path fragments before {@link
   * ResultSink} accepts them.
   */
  public StateMachine buildAndBubbleUpResult(Tasks tasks) {
    resultSink.acceptPathFragmentsWithoutPackageFragment(
        pathFragmentsWithPackageFragment.build().parallelStream()
            .map(p -> p.relativeTo(globDescriptor.getPackageId().getPackageFragment()))
            .collect(toImmutableSet()));
    return DONE;
  }

  /**
   * Container which holds all constant information needed for globbing.
   *
   * <p>This object is created and passed into {@link FragmentProducer} so that we only need one
   * reference of {@link GlobDetail} downstream.
   */
  @AutoValue
  abstract static class GlobDetail {
    static GlobDetail create(
        PackageIdentifier packageIdentifier,
        Root packageRoot,
        ImmutableList<String> patternFragments,
        boolean containsMultipleDoubleStars,
        ImmutableSet<PathFragment> ignoredPackagePrefixesPatterns,
        ConcurrentHashMap<String, Pattern> regexPatternCache,
        Globber.Operation globOperation) {
      return new AutoValue_GlobComputationProducer_GlobDetail(
          packageIdentifier,
          packageRoot,
          patternFragments,
          containsMultipleDoubleStars,
          ignoredPackagePrefixesPatterns,
          regexPatternCache,
          globOperation);
    }

    abstract PackageIdentifier packageIdentifier();

    abstract Root packageRoot();

    abstract ImmutableList<String> patternFragments();

    /**
     * When multiple {@code **}s appear in pattern fragments, a set is created to track visited glob
     * subtasks in order to prevent duplicate work.
     *
     * <p>See {@link FragmentProducer#visitedGlobSubTasks} for more details.
     */
    abstract boolean containsMultipleDoubleStars();

    abstract ImmutableSet<PathFragment> ignoredPackagePrefixesPatterns();

    abstract ConcurrentHashMap<String, Pattern> regexPatternCache();

    abstract Globber.Operation globOperation();
  }
}