validator/graph.cc

// Copyright 2026 Google LLC
//
// 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
//
//    https://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.
//

#include "validator/graph.h"

#include <cstddef>
#include <memory>
#include <optional>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#include "absl/base/nullability.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/status/status.h"
#include "absl/status/status_macros.h"
#include "absl/status/statusor.h"
#include "absl/strings/match.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_join.h"
#include "absl/strings/string_view.h"
#include "assertion/hashed_uri_validator.h"
#include "constants/ingredient_relationships.h"
#include "constants/labels.h"
#include "constants/status_codes.h"
#include "jumbf/box.h"
#include "proto/assertion.pb.h"
#include "proto/bmff_based_hash_assertion.pb.h"
#include "proto/boxes_hash_assertion.pb.h"
#include "proto/collection_data_hash_assertion.pb.h"
#include "proto/data_hash_assertion.pb.h"
#include "proto/generator_info.pb.h"
#include "proto/hashed_uri.pb.h"
#include "proto/ingredient_assertion.pb.h"
#include "proto/manifest.pb.h"
#include "proto/validation_result.pb.h"
#include "proto/validation_status.pb.h"
#include "uuid/uuid.h"
#include "validator/graph_internals.h"
#include "validator/tracker.h"

namespace credentio {
namespace {

template <typename T>
const Manifest* GetManifest(const T* result, absl::string_view label) {
  if (result->active_manifest().label() == label) {
    return &result->active_manifest();
  }
  for (const auto& ingredient_manifest : result->ingredient_manifests()) {
    if (ingredient_manifest.label() == label) {
      return &ingredient_manifest;
    }
  }
  return nullptr;
}

bool IsIngredientAssertion(const Assertion& assertion) {
  return assertion.has_ingredient_v3();
}

// Returns true if the given label is a hard binding assertion label.
// Does not match multi-asset hash assertions or the "part hash" assertions they
// reference.

// Returns true if the given label is for a hard binding assertion, a
// multi-asset hash assertion, or a "part hash" assertion.

std::optional<HashedUri> GetIngredientManifestHashedUri(
    const Assertion& assertion) {
  if (assertion.ingredient_v3().has_active_manifest()) {
    return assertion.ingredient_v3().active_manifest();
  }
  return std::nullopt;
}

absl::string_view GetIngredientRelationship(const Assertion& assertion) {
  return assertion.ingredient_v3().relationship();
}

std::string GetAssertionUri(absl::string_view manifest_label,
                            const Assertion& assertion) {
  return absl::StrJoin({absl::StrCat(kManifestStoreUrlPrefix, manifest_label),
                        kAssertionStoreLabel, assertion.label()},
                       kManifestLabelDelimiter);
}

// No failures are recorded in the tracker for this method as these failures
// are recorded during the ValidateNode call.
std::optional<std::string> GetHardBindingUri(
    const PartialValidationResultProto& result,
    absl::string_view manifest_label, ValidationTracker& tracker) {
  if (manifest_label.empty()) {
    return std::nullopt;
  }
  auto* manifest_with_content_bindings = GetManifest(&result, manifest_label);
  if (manifest_with_content_bindings == nullptr) {
    return std::nullopt;
  }

  std::optional<std::string> uri;
  for (const auto& assertion : manifest_with_content_bindings->assertions()) {
    if ((assertion.has_bmff_based_hash() || assertion.has_boxes_hash() ||
         assertion.has_data_hash() || assertion.has_collection_data_hash()) &&
        !absl::StrContains(assertion.label(), ".part")) {
      uri = GetAssertionUri(manifest_label, assertion);
      break;
    }
  }
  return uri;
}

// No failures are recorded in the tracker for this method as these failures
// are recorded during the ValidateNode call.
std::optional<std::string> GetMultiAssetHashUri(
    const PartialValidationResultProto& result,
    absl::string_view manifest_label, ValidationTracker& tracker) {
  if (manifest_label.empty()) {
    return std::nullopt;
  }
  auto* manifest_with_content_bindings = GetManifest(&result, manifest_label);
  if (manifest_with_content_bindings == nullptr) {
    return std::nullopt;
  }

  std::optional<std::string> uri;
  for (const auto& assertion : manifest_with_content_bindings->assertions()) {
    if (assertion.has_multi_asset_hash()) {
      uri = GetAssertionUri(manifest_label, assertion);
      break;
    }
  }
  return uri;
}

void SetHardBindingUri(absl::string_view manifest_with_content_bindings_label,
                       PartialValidationResultProto& result) {
  ValidationTracker tracker(result.mutable_active_manifest());

  if (result.active_manifest().label().empty()) {
    return;
  }
  if (auto hard_binding_uri = GetHardBindingUri(
          result, manifest_with_content_bindings_label, tracker);
      hard_binding_uri.has_value()) {
    result.set_hard_binding_uri(*hard_binding_uri);
  }
  if (auto multi_asset_hash_uri = GetMultiAssetHashUri(
          result, manifest_with_content_bindings_label, tracker);
      multi_asset_hash_uri.has_value()) {
    result.set_multi_asset_hash_uri(*multi_asset_hash_uri);
  }
}

// Returns the containing manifest path from the given assertion path, or
// nullopt if the assertion path is invalid.
std::optional<absl::string_view> ManifestPathFromAssertionPath(
    absl::string_view path) {
  // Absolute assertion path should look like `/c2pa/<manifest
  // label>/c2pa.assertions/...`. Find the position of the third slash to
  // extract the manifest path.
  if (path.empty() || path[0] != '/') {
    return std::nullopt;
  }
  size_t second_slash = path.find('/', 1);
  if (second_slash == std::string::npos) {
    return std::nullopt;
  }
  size_t third_slash = path.find('/', second_slash + 1);
  if (third_slash == std::string::npos) {
    return std::nullopt;
  }
  return path.substr(0, third_slash);
}

absl::string_view ManifestLabel(const jumbf::SuperBox& node) {
  return node.description.label.value_or("");
}

std::string ManifestPath(const jumbf::SuperBox& node) {
  return absl::StrCat("/c2pa/", ManifestLabel(node));
}

// Applies checks based on the manifest type, returning true if processing
// should continue.
bool CheckManifestType(Manifest& manifest, credentio::Uuid type_uuid,
                       std::string* manifest_with_content_bindings_label,
                       ValidationTracker& tracker) {
  if (type_uuid == kStandardManifestUuid) {
    if (manifest_with_content_bindings_label->empty()) {
      // This is either the active manifest or the first standard manifest
      // found by following the chain of parent ingredients from the active
      // manifest.
      *manifest_with_content_bindings_label = manifest.label();
    }
    return true;
  }
  if (type_uuid == kUpdateManifestUuid) {
    // Update manifest checks are performed in the assertion validator.
    manifest.set_is_update_manifest(true);
    return true;
  }
  if (type_uuid == kCompressedManifestUuid) {
    tracker.RecordFailure(
        FailureStatusCode::kGoogleUnsupportedManifestType,
        {.explanation = "Compressed manifests not supported"});
    return false;
  }
  if (type_uuid == kTimestampManifestUuid) {
    // No need to support time-stamp manifests (deprecated in C2PA 2.2).
    tracker.RecordFailure(FailureStatusCode::kGoogleUnsupportedManifestType,
                          {.explanation = "Timestamp manifests not supported"});
    return false;
  }
  tracker.RecordFailure(
      FailureStatusCode::kGoogleUnsupportedManifestType,
      {.explanation =
           absl::StrCat("Unrecognized manifest type: ", type_uuid.ToString())});
  return false;
}

// Returns true if the manifest label uses a legacy (pre-C2PA-2.1) format.
bool IsLegacyManifestLabel(absl::string_view manifest_label) {
  return !absl::StartsWith(manifest_label, "urn:c2pa");
}

}  // namespace

absl::StatusOr<std::unique_ptr<PartialValidationResultProto>>
ManifestGraph::Validate() {
  ABSL_RETURN_IF_ERROR(ValidateGraph());
  ABSL_ASSIGN_OR_RETURN(auto result, ValidatePostProcess());
  // At this point, the set of redacted assertions and the set of ingredient
  // manifests should be fully populated. We can perform the second pass of the
  // ingredient validation algorithm in
  // https://spec.c2pa.org/specifications/specifications/2.4/specs/C2PA_Specification.html#_performing_explicit_validation.
  return ValidateWithRedactions(std::move(result));
}

absl::StatusOr<std::unique_ptr<PartialValidationResultProto>>
ManifestGraph::ValidatePostProcess() {
  auto result = std::make_unique<PartialValidationResultProto>();
  for (const auto& ingredient_manifest_path : ingredient_manifest_paths_) {
    ABSL_ASSIGN_OR_RETURN(auto manifest_state,
                          GetValidatedManifestState(ingredient_manifest_path));
    absl::flat_hash_set<std::pair<absl::string_view, absl::string_view>>
        existing_failures;
    existing_failures.reserve(
        manifest_state->manifest.validation().failures_size());
    for (const auto& failure :
         manifest_state->manifest.validation().failures()) {
      existing_failures.insert(std::make_pair(failure.code(), failure.url()));
    }
    for (const IngredientAssertion& assertion :
         manifest_state->referencing_ingredient_assertions) {
      PropagateFailuresFromIngredientAssertion(
          assertion.assertion->ingredient_v3(),
          *manifest_state->manifest.mutable_validation(), existing_failures);
    }
    *result->add_ingredient_manifests() = std::move(manifest_state->manifest);
  }
  ABSL_ASSIGN_OR_RETURN(
      auto active_manifest_state,
      GetValidatedManifestState(ManifestPath(active_manifest_)));
  *result->mutable_active_manifest() =
      std::move(active_manifest_state->manifest);
  SetHardBindingUri(manifest_with_content_bindings_label_, *result);
  return result;
}

std::optional<std::string> ManifestGraph::ProcessIngredientAssertion(
    const Assertion& assertion, absl::string_view manifest_path,
    absl::string_view default_algorithm, ValidationTracker& tracker) {
  const std::string assertion_url = absl::StrCat(
      kAssertionStoreLabel, kManifestLabelDelimiter, assertion.label());
  std::optional<HashedUri> manifest_hashed_uri =
      GetIngredientManifestHashedUri(assertion);
  if (!manifest_hashed_uri.has_value()) {
    // Record informational code if the ingredient assertion does not have
    // an `active_manifest` field, unless relationship is `inputTo` (Step
    // 7-a-iii in the algorithm).
    if (GetIngredientRelationship(assertion) !=
        kIngredientRelationshipInputTo) {
      tracker.RecordInformational(
          InformationalStatusCode::kIngredientUnknownProvenance,
          {.url = assertion_url});
    }
    return std::nullopt;
  }
  auto absolute_path = uri_resolver_.GetAbsolutePathFromUri(
      manifest_hashed_uri->url(), manifest_path);
  if (!absolute_path.ok()) {
    tracker.RecordFailure(FailureStatusCode::kIngredientManifestMissing,
                          {.url = assertion_url});
    return std::nullopt;
  }
  if (assertion.ingredient_v3().has_claim_signature()) {
    // Validate the claim signature hash.
    const auto& claim_signature = assertion.ingredient_v3().claim_signature();
    HashedUriValidator claim_signature_hash_validator(
        std::string(manifest_path), uri_resolver_, &hash_checker_factory_);
    claim_signature_hash_validator.SetErrorCodes(HashedUriValidator::Codes{
        .missing = FailureStatusCode::kIngredientClaimSignatureMissing,
        .mismatch = FailureStatusCode::kIngredientClaimSignatureMismatch});
    claim_signature_hash_validator.SetDefaultAlgorithm(
        std::string(default_algorithm));
    auto path = claim_signature_hash_validator.Validate(claim_signature,
                                                        assertion_url, tracker);
    if (!path.has_value()) {
      return std::nullopt;  // Validation failure status has been recorded.
    }
    tracker.RecordSuccess(SuccessStatusCode::kIngredientClaimSignatureValidated,
                          {.url = assertion_url});
  } else {
    // Validate the manifest hash.
    HashedUriValidator manifest_hash_validator(
        std::string(manifest_path), uri_resolver_, &hash_checker_factory_);
    manifest_hash_validator.SetErrorCodes(HashedUriValidator::Codes{
        .missing = FailureStatusCode::kIngredientManifestMissing,
        .mismatch = FailureStatusCode::kIngredientManifestMismatch});
    manifest_hash_validator.SetDefaultAlgorithm(std::string(default_algorithm));
    auto path = manifest_hash_validator.Validate(*manifest_hashed_uri,
                                                 assertion_url, tracker);
    if (!path.has_value()) {
      return std::nullopt;  // Validation failure status has been recorded.
    }
    tracker.RecordSuccess(SuccessStatusCode::kIngredientManifestValidated,
                          {.url = assertion_url});
  }
  return *absolute_path;
}

ManifestGraph::ManifestState& ManifestGraph::GetOrCreateManifestState(
    absl::string_view path) {
  auto [it, inserted] = manifests_.insert({std::string(path), nullptr});
  if (inserted) {
    it->second = std::make_unique<ManifestState>();
  }
  return *it->second;
}

absl::StatusOr<ManifestGraph::ManifestState* absl_nonnull>
ManifestGraph::GetValidatedManifestState(absl::string_view path) {
  auto it = manifests_.find(path);
  if (it == manifests_.end()) {
    return absl::InternalError(
        absl::StrCat("manifest state not found: ", path));
  }
  if (it->second->validation_state != InternalValidationState::kValidated) {
    return absl::InternalError(
        absl::StrCat("manifest is not yet validated: ", path));
  }
  return it->second.get();
}

absl::Status ManifestGraph::ValidateGraph() {
  std::stack<const jumbf::SuperBox*> to_visit;
  to_visit.push(&active_manifest_);
  bool is_active_manifest = true;
  while (!to_visit.empty()) {
    const jumbf::SuperBox* node = to_visit.top();
    to_visit.pop();
    ABSL_RETURN_IF_ERROR(ValidateNode(*node,
                                      /*is_active_manifest=*/is_active_manifest,
                                      to_visit));
    is_active_manifest = false;
  }
  return absl::OkStatus();
}

// Validates the claim and assertions for the given "node" that represents a
// manifest in the manifest graph. Calling this function for a node is similar
// to jumping to Step 3 in the ingredient validation algorithm in
// https://spec.c2pa.org/specifications/specifications/2.4/specs/C2PA_Specification.html#_performing_explicit_validation
// for a target manifest represented by this node in the manifest graph.
//
// The method:
// * Locates and validates the claim (Step 4 in the algorithm).
// * Updates the set of redacted assertions (Step 5 in the algorithm).
// * Validates all assertions in the claim (Step 6 in the algorithm).
// * Finally, the method pushes all eligible ingredient manifests onto the
//   `to_visit` stack (Step 7 in the algorithm).
absl::Status ManifestGraph::ValidateNode(
    const jumbf::SuperBox& node, bool is_active_manifest,
    std::stack<const jumbf::SuperBox*>& to_visit) {
  absl::string_view manifest_label = ManifestLabel(node);
  std::string manifest_path = ManifestPath(node);
  ManifestState& manifest_state = GetOrCreateManifestState(manifest_path);
  if (manifest_state.validation_state == InternalValidationState::kValidated) {
    return absl::OkStatus();
  }
  if (!is_active_manifest) ingredient_manifest_paths_.push_back(manifest_path);
  InternalValidationStateLock validation_state_lock(&manifest_state);

  Manifest& manifest = manifest_state.manifest;
  manifest.set_label(manifest_label);
  ValidationTracker tracker(&manifest);
  {
    if (IsLegacyManifestLabel(manifest_label)) {
      tracker.RecordFailure(
          FailureStatusCode::kGoogleUnsupportedSpecVersion,
          {.explanation = "deprecated manifest label format"});
      return absl::OkStatus();
    }
    if (!CheckManifestType(manifest, node.description.type_uuid,
                           &manifest_with_content_bindings_label_, tracker)) {
      return absl::OkStatus();
    }

    auto validated_claim = claim_validator_.Validate(node, tracker);
    if (!validated_claim.has_value()) {
      return absl::OkStatus();
    }
    *manifest.mutable_claim() = *std::move(validated_claim);
    // Update the set of redacted assertions.
    for (const auto& assertion : manifest.claim().redacted_assertions()) {
      ProcessRedaction(assertion, manifest_path, tracker);
    }
    //
    // Validate assertions and populate `manifest.assertions`.
    assertion_validator_.ValidateClaimAssertions(
        uri_resolver_, manifest_state.redacted_assertions, manifest, tracker);
    // Find ingredient manifests from the validated ingredient assertions and
    // add them to the `ingredients` field of the result.
    std::vector<std::string> ingredients;
    for (const auto& assertion : manifest.assertions()) {
      if (IsIngredientAssertion(assertion)) {
        auto ingredient_manifest_path = ProcessIngredientAssertion(
            assertion, manifest_path,
            /*default_algorithm=*/
            manifest.claim().default_algorithm(), tracker);
        if (ingredient_manifest_path.has_value()) {
          auto ingredient_manifest_box =
              uri_resolver_.ResolvePath(*ingredient_manifest_path);
          if (!ingredient_manifest_box.ok() ||
              *ingredient_manifest_box == nullptr) {
            tracker.RecordFailure(
                FailureStatusCode::kIngredientManifestMissing,
                {.url =
                     absl::StrCat(kAssertionStoreLabel, kManifestLabelDelimiter,
                                  assertion.label()),
                 .explanation = absl::StrCat(
                     "Failed to resolve the ingredient manifest URI: ",
                     *ingredient_manifest_path)});
          } else {
            ManifestState& ingredient_manifest_state =
                GetOrCreateManifestState(*ingredient_manifest_path);
            ingredient_manifest_state.referencing_ingredient_assertions
                .push_back(IngredientAssertion{.assertion = &assertion,
                                               .assertion_uri = GetAssertionUri(
                                                   manifest_label, assertion)});
            // Update the set of ingredients that will be recursed into.
            if (ingredient_manifest_state.validation_state !=
                InternalValidationState::kValidated) {
              ingredients.push_back(*ingredient_manifest_path);
            }
          }
        }
      }
    }
    // Push ingredient manifests onto the stack for depth-first traversal.
    for (; !ingredients.empty(); ingredients.pop_back()) {
      const std::string& ingredient_manifest = ingredients.back();
      auto ingredient_manifest_box =
          uri_resolver_.ResolvePath(ingredient_manifest);
      if (!ingredient_manifest_box.ok() ||
          *ingredient_manifest_box == nullptr) {
        // This should never happen because we have already validated the
        // ingredient manifest URI.
        continue;
      }
      to_visit.push(*ingredient_manifest_box);
    }
  }
  if (manifest.validation().failures_size() == 0 &&
      manifest.validation().successes_size() == 0) {
    tracker.RecordFailure(FailureStatusCode::kGoogleInternalError,
                          {.explanation = "No failure or success "
                                          "status codes were recorded."});
  }
  return absl::OkStatus();
}

absl::StatusOr<std::unique_ptr<PartialValidationResultProto>>
ManifestGraph::ValidateWithRedactions(
    std::unique_ptr<PartialValidationResultProto> result) {
  return result;
}

void ManifestGraph::ProcessRedaction(absl::string_view redacted_assertion_uri,
                                     absl::string_view manifest_path,
                                     ValidationTracker& tracker) {
  // Resolve the redacted assertion URI to an absolute path before adding it
  // to the set.
  absl::StatusOr<std::string> absolute_path =
      uri_resolver_.GetAbsolutePathFromUri(redacted_assertion_uri,
                                           manifest_path);
  if (!absolute_path.ok()) {
    // Malformed URI.
    tracker.RecordFailure(FailureStatusCode::kAssertionMissing, {});
    return;
  }
  // Check if the redacted assertion URI points into the manifest whose claim
  // redacted it.
  if (absl::StartsWith(*absolute_path, manifest_path)) {
    tracker.RecordFailure(FailureStatusCode::kAssertionSelfRedacted, {});
    return;
  }
  std::optional<absl::string_view> redacted_assertion_manifest_path =
      ManifestPathFromAssertionPath(*absolute_path);
  if (!redacted_assertion_manifest_path.has_value()) {
    // Malformed path.
    tracker.RecordFailure(FailureStatusCode::kAssertionMissing, {});
    return;
  }
  GetOrCreateManifestState(*redacted_assertion_manifest_path)
      .redacted_assertions.insert(*absolute_path);
}

ManifestGraph::InternalValidationStateLock::InternalValidationStateLock(
    ManifestState* absl_nonnull manifest_state)
    : manifest_state_(*manifest_state) {
  DCHECK(manifest_state_.validation_state ==
         InternalValidationState::kUnvalidated);
  manifest_state_.validation_state = InternalValidationState::kBeingValidated;
}

ManifestGraph::InternalValidationStateLock::~InternalValidationStateLock() {
  manifest_state_.validation_state = InternalValidationState::kValidated;
}
}  // namespace credentio