(** PubGrub: A Dependency Resolution Algorithm

    This library implements the PubGrub algorithm, a next-generation version solving algorithm
    designed for package managers. It efficiently finds a set of package versions that satisfy
    all dependencies, or provides a clear explanation of why no solution exists.
*)

(** {1 Core Types} *)

(** Package identifier. Must be comparable and displayable. *)
module type PACKAGE_ID = sig
  type t
  (** The package identifier type. *)

  val compare : t -> t -> int
  (** Compare two package identifiers. *)

  val to_string : t -> string
  (** Convert a package identifier to a string. *)
end

(** Version type. Must be orderable and displayable. *)
module type VERSION = sig
  type t
  (** The version type. *)

  val compare : t -> t -> int
  (** Compare two versions. Newer versions should be greater. *)

  val to_string : t -> string
  (** Convert a version to a string. *)
end

(** {1 Version Sets and Ranges} *)

(** A set or range of versions. *)
module type VERSION_SET = sig
  type t
  (** The version set type. *)

  type version
  (** The version type. *)

  val empty : t
  (** The empty set. *)

  val any : t
  (** The set of all versions. *)

  val singleton : version -> t
  (** A set containing exactly one version. *)

  val union : t -> t -> t
  (** Union of two version sets. *)

  val intersection : t -> t -> t
  (** Intersection of two version sets. *)

  val complement : t -> t
  (** Complement of a version set. *)

  val is_empty : t -> bool
  (** Whether the set is empty. *)

  val contains : version -> t -> bool
  (** Whether a version is in the set. *)

  val subset_of : t -> t -> bool
  (** Whether the first set is a subset of the second. *)

  val is_disjoint : t -> t -> bool
  (** Whether two sets are disjoint. *)

  val to_string : t -> string
  (** Convert a version set to a string. *)
end

(** {1 Terms and Constraints} *)

(** A term is either a positive or negative constraint on a package version. *)
type ('v, 'vs) term =
  | Positive of 'vs  (** The package version must be in this set. *)
  | Negative of 'vs  (** The package version must not be in this set. *)

(** Term operations. *)
module Term : sig
  type ('v, 'vs) t = ('v, 'vs) term

  val any : 'vs -> ('v, 'vs) t
  (** A term that matches any version in the given set. *)

  val empty : 'vs -> ('v, 'vs) t
  (** A term that matches no version in the given set. *)

  val exact : 'v -> ('v -> 'vs) -> ('v, 'vs) t
  (** A term requiring exactly this version. *)

  val negate : ('v, 'vs) t -> ('v, 'vs) t
  (** Negate a term. *)

  val contains : 'v -> ('v -> 'vs -> bool) -> ('v, 'vs) t -> bool
  (** Whether a version satisfies a term. *)

  val intersection : ('vs -> 'vs -> 'vs) -> ('vs -> 'vs) -> ('v, 'vs) t -> ('v, 'vs) t -> ('v, 'vs) t
  (** Intersection of two terms. *)

  val union : ('vs -> 'vs -> 'vs) -> ('vs -> 'vs -> 'vs) -> ('vs -> 'vs) -> ('vs -> bool) -> ('v, 'vs) t -> ('v, 'vs) t -> ('v, 'vs) t
  (** Union of two terms. *)

  val is_positive : ('v, 'vs) t -> bool
  (** Whether a term is positive. *)

  val to_string : ('v -> string) -> ('vs -> string) -> ('v, 'vs) t -> string
  (** Convert a term to a string. *)
end

(** {1 Incompatibilities} *)

(** An incompatibility is a set of terms that cannot be satisfied together. *)
type ('p, 'v, 'vs, 'meta) incompatibility = {
  terms : (('p * ('v, 'vs) term) list);
  (** The terms that cannot be satisfied together. *)
  
  cause : ('p, 'v, 'vs, 'meta) incompatibility_cause;
  (** The reason this incompatibility exists. *)
}

(** The cause of an incompatibility. *)
and ('p, 'v, 'vs, 'meta) incompatibility_cause =
  | Root of 'p * 'v
  (** Incompatibility derived from root package requirement. *)
  
  | NoVersions of 'p * 'vs
  (** No versions satisfy the constraint. *)
  
  | Dependency of 'p * 'vs * 'p * 'vs
  (** Package depends on another package. *)
  
  | Derived of int * int
  (** Derived from two other incompatibilities. *)
  
  | External of 'p * 'vs * 'meta
  (** External incompatibility with custom metadata. *)

(** {1 Partial Solutions} *)

(** A partial solution represents the current state of the solver. *)
type ('p, 'v, 'vs) partial_solution = {
  decision_level : int;
  (** Current decision level. *)
  
  decisions : ('p * 'v) list;
  (** Package versions that have been selected. *)
  
  assignments : ('p * ('v, 'vs) term * int * bool) list;
  (** Terms derived from decisions. Each tuple contains:
      - The package
      - The term
      - The decision level
      - Whether this is a decision (true) or derived (false) *)
}

(** {1 Dependency Provider} *)

(** Interface for a dependency provider. *)
module type DEPENDENCY_PROVIDER = sig
  type package_id
  (** The package identifier type. *)

  type version
  (** The package version type. *)

  type version_set
  (** The version set type. *)

  type error
  (** The type of errors that can occur. *)

  val get_root_package : unit -> package_id
  (** Get the root package identifier. *)

  val get_root_version : unit -> version
  (** Get the version of the root package. *)

  val available_versions : package_id -> version list
  (** List all available versions of a package in descending order (newest first). *)

  val get_dependencies :
    package_id -> version -> ((package_id * version_set) list, error) result
  (** Get the dependencies of a package at a specific version. *)

  val choose_version :
    package_id -> version_set -> version option
  (** Choose a version for a package given a constraint. *)
end

(** {1 Solver Configuration} *)

(** Configuration options for the solver. *)
type 'a config = {
  max_iterations : int option;
  (** Maximum number of iterations before giving up. None means no limit. *)
}

(** Default configuration with no iteration limit. *)
val default_config : 'a config

(** {1 Main Solver Interface} *)

(** Types and operations for the PubGrub solver. *)
module type SOLVER = sig
  type package_id
  (** Package identifier type. *)

  type version
  (** Version type. *)

  type version_set
  (** Version set type. *)

  type metadata
  (** Custom metadata type for external incompatibilities. *)

  (** Error types. *)
  type error =
    | Unsatisfiable of {
        explanation : string;
        (** A human-readable explanation of why no solution exists. *)
      }
    | DependencyProviderError of {
        package : package_id;
        version : version;
        message : string;
        (** An error from the dependency provider. *)
      }
    | MaxIterationsExceeded
    (** The solver exceeded the maximum number of iterations. *)

  (** The solution type: a list of packages and their selected versions. *)
  type solution = (package_id * version) list

  (** Solve dependencies for a package.
      Returns either a solution or an error explaining why no solution exists. *)
  val solve :
    (module DEPENDENCY_PROVIDER with
      type package_id = package_id and
      type version = version and
      type version_set = version_set and
      type error = string) ->
    'a config ->
    (solution, error) result

  (** Generate a human-readable explanation of an error. *)
  val explain_error : error -> string
end

(** {1 Functor Interface} *)

(** Create a solver with the given types. *)
module Make
    (P : PACKAGE_ID)
    (V : VERSION)
    (VS : VERSION_SET with type version = V.t) : 
  SOLVER
    with type package_id = P.t
     and type version = V.t
     and type version_set = VS.t
     and type metadata = string