// Copyright (C) 2020 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.plugins.codeowners.backend;

import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.ImmutableSet.toImmutableSet;
import static java.util.Objects.requireNonNull;
import static java.util.stream.Collectors.toSet;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;
import com.google.common.flogger.FluentLogger;
import com.google.gerrit.entities.BranchNameKey;
import com.google.gerrit.entities.Project;
import com.google.gerrit.plugins.codeowners.backend.config.CodeOwnersPluginConfiguration;
import com.google.gerrit.server.logging.Metadata;
import com.google.gerrit.server.logging.TraceContext;
import com.google.gerrit.server.logging.TraceContext.TraceTimer;
import com.google.gerrit.server.project.ProjectCache;
import com.google.gerrit.server.project.ProjectState;
import com.google.inject.Inject;
import com.google.inject.Singleton;
import java.nio.file.Path;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Stream;
import org.eclipse.jgit.lib.ObjectId;

/**
 * Class to compute the code owners for a path from a {@link CodeOwnerConfig}.
 *
 * <p>Code owners from inherited code owner configs are not considered.
 */
public class PathCodeOwners {
  private static final FluentLogger logger = FluentLogger.forEnclosingClass();

  @Singleton
  public static class Factory {
    private final ProjectCache projectCache;
    private final CodeOwnersPluginConfiguration codeOwnersPluginConfiguration;
    private final CodeOwners codeOwners;

    @Inject
    Factory(
        ProjectCache projectCache,
        CodeOwnersPluginConfiguration codeOwnersPluginConfiguration,
        CodeOwners codeOwners) {
      this.projectCache = projectCache;
      this.codeOwnersPluginConfiguration = codeOwnersPluginConfiguration;
      this.codeOwners = codeOwners;
    }

    public PathCodeOwners create(CodeOwnerConfig codeOwnerConfig, Path absolutePath) {
      requireNonNull(codeOwnerConfig, "codeOwnerConfig");
      return new PathCodeOwners(
          projectCache,
          codeOwners,
          codeOwnerConfig,
          absolutePath,
          getMatcher(codeOwnerConfig.key()));
    }

    public Optional<PathCodeOwners> create(
        CodeOwnerConfig.Key codeOwnerConfigKey, ObjectId revision, Path absolutePath) {
      return codeOwners
          .get(codeOwnerConfigKey, revision)
          .map(
              codeOwnerConfig ->
                  new PathCodeOwners(
                      projectCache,
                      codeOwners,
                      codeOwnerConfig,
                      absolutePath,
                      getMatcher(codeOwnerConfigKey)));
    }

    /**
     * Gets the {@link PathExpressionMatcher} that should be used for the specified code owner
     * config.
     *
     * <p>Checks which {@link CodeOwnerBackend} is responsible for the specified code owner config
     * and retrieves the {@link PathExpressionMatcher} from it.
     *
     * <p>If the {@link CodeOwnerBackend} doesn't support path expressions and doesn't provide a
     * {@link PathExpressionMatcher} a {@link PathExpressionMatcher} that never matches is returned.
     * This way {@link CodeOwnerSet}s that have path expressions are ignored and will not have any
     * effect.
     *
     * @param codeOwnerConfigKey the key of the code owner config for which the path expression
     *     matcher should be returned
     * @return the {@link PathExpressionMatcher} that should be used for the specified code owner
     *     config
     */
    private PathExpressionMatcher getMatcher(CodeOwnerConfig.Key codeOwnerConfigKey) {
      CodeOwnerBackend codeOwnerBackend =
          codeOwnersPluginConfiguration.getBackend(codeOwnerConfigKey.branchNameKey());
      return codeOwnerBackend
          .getPathExpressionMatcher()
          .orElse((pathExpression, relativePath) -> false);
    }
  }

  private final ProjectCache projectCache;
  private final CodeOwners codeOwners;
  private final CodeOwnerConfig codeOwnerConfig;
  private final Path path;
  private final PathExpressionMatcher pathExpressionMatcher;

  private PathCodeOwnersResult pathCodeOwnersResult;

  private PathCodeOwners(
      ProjectCache projectCache,
      CodeOwners codeOwners,
      CodeOwnerConfig codeOwnerConfig,
      Path path,
      PathExpressionMatcher pathExpressionMatcher) {
    this.projectCache = requireNonNull(projectCache, "projectCache");
    this.codeOwners = requireNonNull(codeOwners, "codeOwners");
    this.codeOwnerConfig = requireNonNull(codeOwnerConfig, "codeOwnerConfig");
    this.path = requireNonNull(path, "path");
    this.pathExpressionMatcher = requireNonNull(pathExpressionMatcher, "pathExpressionMatcher");

    checkState(path.isAbsolute(), "path %s must be absolute", path);
  }

  /** Returns the local code owner config. */
  public CodeOwnerConfig getCodeOwnerConfig() {
    return codeOwnerConfig;
  }

  /**
   * Resolves the {@link #codeOwnerConfig}.
   *
   * <p>Resolving means that:
   *
   * <ul>
   *   <li>non-matching per-file code owner sets are dropped (since code owner sets that do not
   *       match the {@link #path} are not relevant)
   *   <li>imported code owner configs are loaded and replaced with the parts of them which should
   *       be imported (depends on the {@link CodeOwnerConfigImportMode}) and that are relevant for
   *       the {@link #path}
   *   <li>global code owner sets are dropped if any matching per-file code owner set has the
   *       ignoreGlobalAndParentCodeOwners flag set to {@code true} (since in this case global code
   *       owners should be ignored and then the global code owner sets are not relevant)
   *   <li>the ignoreParentCodeOwners flag is set to {@code true} if any matching per-file code
   *       owner set has the ignoreGlobalAndParentCodeOwners flag set to true (since in this case
   *       code owners from parent configurations should be ignored)
   * </ul>
   *
   * <p>When resolving imports, cycles are detected and code owner configs that have been seen
   * already are not evaluated again.
   *
   * <p>Non-resolvable imports are silently ignored.
   *
   * <p>Imports that are loaded from the same project/branch as {@link #codeOwnerConfig} are
   * imported from the same revision from which {@link #codeOwnerConfig} was loaded. Imports that
   * are loaded from other projects/branches are imported from the current revision. If several
   * imports are loaded from the same project/branch we guarantee that they are all loaded from the
   * same revision, even if the current revision is changed by a concurrent request while the
   * resolution is being performed.
   *
   * <p>Imports from other projects are always loaded from the same branch from which the importing
   * code owner config was loaded.
   *
   * @return the resolved code owner config
   */
  public PathCodeOwnersResult resolveCodeOwnerConfig() {
    if (this.pathCodeOwnersResult != null) {
      return this.pathCodeOwnersResult;
    }

    try (TraceTimer traceTimer =
        TraceContext.newTimer(
            "Resolve code owner config",
            Metadata.builder()
                .projectName(codeOwnerConfig.key().project().get())
                .filePath(path.toString())
                .build())) {
      logger.atFine().log(
          "resolve code owners for %s from code owner config %s", path, codeOwnerConfig.key());

      CodeOwnerConfig.Builder resolvedCodeOwnerConfigBuilder =
          CodeOwnerConfig.builder(codeOwnerConfig.key(), codeOwnerConfig.revision());

      // Add all data from the importing code owner config.
      resolvedCodeOwnerConfigBuilder.setIgnoreParentCodeOwners(
          codeOwnerConfig.ignoreParentCodeOwners());
      getGlobalCodeOwnerSets(codeOwnerConfig)
          .forEach(resolvedCodeOwnerConfigBuilder::addCodeOwnerSet);
      getMatchingPerFileCodeOwnerSets(codeOwnerConfig)
          .forEach(resolvedCodeOwnerConfigBuilder::addCodeOwnerSet);

      List<UnresolvedImport> unresolvedImports =
          resolveImports(codeOwnerConfig, resolvedCodeOwnerConfigBuilder);

      CodeOwnerConfig resolvedCodeOwnerConfig = resolvedCodeOwnerConfigBuilder.build();

      // Remove global code owner sets if any per-file code owner set has the
      // ignoreGlobalAndParentCodeOwners flag set to true.
      // In this case also set ignoreParentCodeOwners to true, so that we do not need to inspect the
      // ignoreGlobalAndParentCodeOwners flags again.
      if (getMatchingPerFileCodeOwnerSets(resolvedCodeOwnerConfig)
          .anyMatch(CodeOwnerSet::ignoreGlobalAndParentCodeOwners)) {
        logger.atFine().log("remove global code owner sets and set ignoreParentCodeOwners to true");
        resolvedCodeOwnerConfig =
            resolvedCodeOwnerConfig
                .toBuilder()
                .setIgnoreParentCodeOwners()
                .setCodeOwnerSets(
                    resolvedCodeOwnerConfig.codeOwnerSets().stream()
                        .filter(codeOwnerSet -> !codeOwnerSet.pathExpressions().isEmpty())
                        .collect(toImmutableSet()))
                .build();
      }

      this.pathCodeOwnersResult =
          PathCodeOwnersResult.create(path, resolvedCodeOwnerConfig, unresolvedImports);
      logger.atFine().log("path code owners result = %s", pathCodeOwnersResult);
      return this.pathCodeOwnersResult;
    }
  }

  /**
   * Resolve the imports of the given code owner config.
   *
   * @param importingCodeOwnerConfig the code owner config for which imports should be resolved
   * @param resolvedCodeOwnerConfigBuilder the builder for the resolved code owner config
   * @return list of unresolved imports, empty list if all imports were successfully resolved
   */
  private List<UnresolvedImport> resolveImports(
      CodeOwnerConfig importingCodeOwnerConfig,
      CodeOwnerConfig.Builder resolvedCodeOwnerConfigBuilder) {
    ImmutableList.Builder<UnresolvedImport> unresolvedImports = ImmutableList.builder();
    try (TraceTimer traceTimer =
        TraceContext.newTimer(
            "Resolve code owner config imports",
            Metadata.builder()
                .projectName(codeOwnerConfig.key().project().get())
                .branchName(codeOwnerConfig.key().ref())
                .filePath(codeOwnerConfig.key().filePath("<default>").toString())
                .build())) {
      // To detect cyclic dependencies we keep track of all seen code owner configs.
      Set<CodeOwnerConfig.Key> seenCodeOwnerConfigs = new HashSet<>();
      seenCodeOwnerConfigs.add(codeOwnerConfig.key());

      // To ensure that code owner configs from the same project/branch are imported from the same
      // revision we keep track of the revisions.
      Map<BranchNameKey, ObjectId> revisionMap = new HashMap<>();
      revisionMap.put(codeOwnerConfig.key().branchNameKey(), codeOwnerConfig.revision());

      Queue<CodeOwnerConfigReference> codeOwnerConfigsToImport = new ArrayDeque<>();
      codeOwnerConfigsToImport.addAll(importingCodeOwnerConfig.imports());
      codeOwnerConfigsToImport.addAll(
          resolvedCodeOwnerConfigBuilder.codeOwnerSets().stream()
              .flatMap(codeOwnerSet -> codeOwnerSet.imports().stream())
              .collect(toImmutableSet()));

      while (!codeOwnerConfigsToImport.isEmpty()) {
        CodeOwnerConfigReference codeOwnerConfigReference = codeOwnerConfigsToImport.poll();
        CodeOwnerConfig.Key keyOfImportedCodeOwnerConfig =
            createKeyForImportedCodeOwnerConfig(
                importingCodeOwnerConfig.key(), codeOwnerConfigReference);
        try (TraceTimer traceTimer2 =
            TraceContext.newTimer(
                "Resolve code owner config import",
                Metadata.builder()
                    .projectName(keyOfImportedCodeOwnerConfig.project().get())
                    .branchName(keyOfImportedCodeOwnerConfig.ref())
                    .filePath(
                        keyOfImportedCodeOwnerConfig
                            .filePath(codeOwnerConfigReference.fileName())
                            .toString())
                    .build())) {
          Optional<ProjectState> projectState =
              projectCache.get(keyOfImportedCodeOwnerConfig.project());
          if (!projectState.isPresent()) {
            unresolvedImports.add(
                UnresolvedImport.create(
                    codeOwnerConfig.key(),
                    keyOfImportedCodeOwnerConfig,
                    codeOwnerConfigReference,
                    String.format(
                        "project %s not found", keyOfImportedCodeOwnerConfig.project().get())));
            continue;
          }
          if (!projectState.get().statePermitsRead()) {
            unresolvedImports.add(
                UnresolvedImport.create(
                    codeOwnerConfig.key(),
                    keyOfImportedCodeOwnerConfig,
                    codeOwnerConfigReference,
                    String.format(
                        "state of project %s doesn't permit read",
                        keyOfImportedCodeOwnerConfig.project().get())));
            continue;
          }

          Optional<ObjectId> revision =
              Optional.ofNullable(revisionMap.get(keyOfImportedCodeOwnerConfig.branchNameKey()));
          logger.atFine().log(
              "import from %s",
              revision.isPresent() ? "revision " + revision.get().name() : "current revision");

          Optional<CodeOwnerConfig> mayBeImportedCodeOwnerConfig =
              revision.isPresent()
                  ? codeOwners.get(keyOfImportedCodeOwnerConfig, revision.get())
                  : codeOwners.getFromCurrentRevision(keyOfImportedCodeOwnerConfig);

          if (!mayBeImportedCodeOwnerConfig.isPresent()) {
            unresolvedImports.add(
                UnresolvedImport.create(
                    codeOwnerConfig.key(),
                    keyOfImportedCodeOwnerConfig,
                    codeOwnerConfigReference,
                    String.format(
                        "code owner config does not exist (revision = %s)",
                        revision.map(ObjectId::name).orElse("current"))));
            continue;
          }

          CodeOwnerConfig importedCodeOwnerConfig = mayBeImportedCodeOwnerConfig.get();
          CodeOwnerConfigImportMode importMode = codeOwnerConfigReference.importMode();
          logger.atFine().log("import mode = %s", importMode.name());

          revisionMap.putIfAbsent(
              keyOfImportedCodeOwnerConfig.branchNameKey(), importedCodeOwnerConfig.revision());

          if (importMode.importIgnoreParentCodeOwners()
              && importedCodeOwnerConfig.ignoreParentCodeOwners()) {
            logger.atFine().log("import ignoreParentCodeOwners flag");
            resolvedCodeOwnerConfigBuilder.setIgnoreParentCodeOwners();
          }

          if (importMode.importGlobalCodeOwnerSets()) {
            logger.atFine().log("import global code owners");
            getGlobalCodeOwnerSets(importedCodeOwnerConfig)
                .forEach(resolvedCodeOwnerConfigBuilder::addCodeOwnerSet);
          }

          if (importMode.importPerFileCodeOwnerSets()) {
            logger.atFine().log("import per-file code owners");
            getMatchingPerFileCodeOwnerSets(importedCodeOwnerConfig)
                .forEach(resolvedCodeOwnerConfigBuilder::addCodeOwnerSet);
          }

          if (importMode.resolveImportsOfImport()
              && seenCodeOwnerConfigs.add(keyOfImportedCodeOwnerConfig)) {
            logger.atFine().log("resolve imports of imported code owner config");
            Set<CodeOwnerConfigReference> transitiveImports = new HashSet<>();
            transitiveImports.addAll(importedCodeOwnerConfig.imports());
            transitiveImports.addAll(
                importedCodeOwnerConfig.codeOwnerSets().stream()
                    .flatMap(codeOwnerSet -> codeOwnerSet.imports().stream())
                    .collect(toImmutableSet()));

            if (importMode == CodeOwnerConfigImportMode.GLOBAL_CODE_OWNER_SETS_ONLY) {
              // If only global code owners should be imported, transitive imports should also only
              // import global code owners, no matter which import mode is specified in the imported
              // code owner configs.
              logger.atFine().log(
                  "import transitive imports with mode %s",
                  CodeOwnerConfigImportMode.GLOBAL_CODE_OWNER_SETS_ONLY);
              transitiveImports =
                  transitiveImports.stream()
                      .map(
                          codeOwnerCfgRef ->
                              CodeOwnerConfigReference.copyWithNewImportMode(
                                  codeOwnerCfgRef,
                                  CodeOwnerConfigImportMode.GLOBAL_CODE_OWNER_SETS_ONLY))
                      .collect(toSet());
            }

            logger.atFine().log("transitive imports = %s", transitiveImports);
            codeOwnerConfigsToImport.addAll(transitiveImports);
          }
        }
      }
    }
    return unresolvedImports.build();
  }

  public static CodeOwnerConfig.Key createKeyForImportedCodeOwnerConfig(
      CodeOwnerConfig.Key keyOfImportingCodeOwnerConfig,
      CodeOwnerConfigReference codeOwnerConfigReference) {
    // if the code owner config reference doesn't have a project, the imported code owner config
    // file is contained in the same project as the importing code owner config
    Project.NameKey project =
        codeOwnerConfigReference.project().orElse(keyOfImportingCodeOwnerConfig.project());

    // if the code owner config reference doesn't have a branch, the imported code owner config file
    // is imported from the same branch in which the importing code owner config is stored
    String branch =
        codeOwnerConfigReference
            .branch()
            .orElse(keyOfImportingCodeOwnerConfig.branchNameKey().branch());

    // if the path of the imported code owner config is relative, it should be resolved against
    // the folder path of the importing code owner config
    Path folderPath =
        keyOfImportingCodeOwnerConfig
            .folderPath()
            .resolve(codeOwnerConfigReference.path())
            .normalize();

    return CodeOwnerConfig.Key.create(
        BranchNameKey.create(project, branch), folderPath, codeOwnerConfigReference.fileName());
  }

  private static Stream<CodeOwnerSet> getGlobalCodeOwnerSets(CodeOwnerConfig codeOwnerConfig) {
    return codeOwnerConfig.codeOwnerSets().stream()
        .filter(codeOwnerSet -> codeOwnerSet.pathExpressions().isEmpty());
  }

  private Stream<CodeOwnerSet> getMatchingPerFileCodeOwnerSets(CodeOwnerConfig codeOwnerConfig) {
    return codeOwnerConfig.codeOwnerSets().stream()
        .filter(codeOwnerSet -> !codeOwnerSet.pathExpressions().isEmpty())
        .filter(codeOwnerSet -> matches(codeOwnerSet, getRelativePath(), pathExpressionMatcher));
  }

  private Path getRelativePath() {
    return codeOwnerConfig.relativize(path);
  }

  /**
   * Whether the given code owner set matches the given path.
   *
   * <p>A path matches the code owner set, if any of its path expressions matches the path.
   *
   * <p>The passed in code owner set must have at least one path expression.
   *
   * @param codeOwnerSet the code owner set for which it should be checked if it matches the given
   *     path, must have at least one path expression
   * @param relativePath path for which it should be checked whether it matches the given owner set;
   *     the path must be relative to the path in which the {@link CodeOwnerConfig} is stored that
   *     contains the code owner set; can be the path of a file or folder; the path may or may not
   *     exist
   * @param matcher the {@link PathExpressionMatcher} that should be used to match path expressions
   *     against the given path
   * @return whether this owner set matches the given path
   */
  @VisibleForTesting
  static boolean matches(
      CodeOwnerSet codeOwnerSet, Path relativePath, PathExpressionMatcher matcher) {
    requireNonNull(codeOwnerSet, "codeOwnerSet");
    requireNonNull(relativePath, "relativePath");
    requireNonNull(matcher, "matcher");
    checkState(!relativePath.isAbsolute(), "path %s must be relative", relativePath);
    checkState(
        !codeOwnerSet.pathExpressions().isEmpty(), "code owner set must have path expressions");

    return codeOwnerSet.pathExpressions().stream()
        .anyMatch(pathExpression -> matcher.matches(pathExpression, relativePath));
  }
}