(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2018 Dynamic Ledger Solutions, Inc. <contact@tezos.com>     *)
(* Copyright (c) 2022 Nomadic Labs. <contact@nomadic-labs.com>               *)
(* Copyright (c) 2023 DaiLambda, Inc. <contact@dailambda.jp>                 *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

(** Models associated to benchmarks have free variables. Some of these
    variables are to be inferred from the empirical data, but some others
    must be provided by other models and correspond to _dependencies_
    of a model upon the result of another one.

    The goal of this module is to take as input a set of models seen as
    sets of free variables and infer back a partial dependency ordering
    among them. In particular, a topological sort of this partial ordering
    yields a scheduling for the inference process that respects cross-model
    dependencies.

    Such a problem does not always have a solution, or can have several
    solutions (ie it is in general ill-posed). When there's more than
    one possible solution, we use a simple heuristic to pick one.
*)

(** Decide dependencies/provides of free variables *)
module Solver : sig
  module Unsolved : sig
    type t

    (** [build name ~fvs_unapplied fvs_applied] builds an unsolved node
        of a benchmark of name [name]. [fvs_unapplied] is the set of
        free variables of the models of the benchmark without workload
        application. [fvs_applied] is the set of free variables of
        the models of the benchmark applied with workloads.
    *)
    val build :
      Namespace.t ->
      fvs_unapplied:Free_variable.Set.t ->
      Free_variable.Set.t ->
      t
  end

  module Solved : sig
    type t = {
      dependencies : Free_variable.Set.t;
      provides : Free_variable.Set.t;
      name : Namespace.t;
    }

    val pp : Format.formatter -> t -> unit
  end

  val solve : Unsolved.t list -> Solved.t list
end

(** Visualization of solutions using Graphviz *)
module Graphviz : sig
  val save : string -> Solver.Solved.t list -> unit
end

(** Dependency graph of benchmarks using dependencies/provides *)
module Graph : sig
  type t

  val is_empty : t -> bool

  (** Which benchmarks provide each variable *)
  type providers_map = Solver.Solved.t list Free_variable.Map.t

  val is_ambiguous : providers_map -> bool

  (** Print out the ambiguity information to stderr *)
  val warn_ambiguities : providers_map -> unit

  type result = {
    (* Graph without ambiguities. The ambiguities are resolved by heuristics *)
    resolved : t;
    (* Graph with possible ambiguity *)
    with_ambiguities : t;
    (* Which benchmarks provide each variable *)
    providers_map : providers_map;
  }

  (** Build dependency graphs *)
  val build : Solver.Solved.t list -> result

  (** Dependency topological folding *)
  val fold : (Solver.Solved.t -> 'a -> 'a) -> t -> 'a -> 'a

  (** Dependency topological iteration *)
  val iter : (Solver.Solved.t -> unit) -> t -> unit

  (** Returns the topological ordered list of [Solver.Sovled.t] *)
  val to_sorted_list : t -> Solver.Solved.t list

  (** Visualize the graph using Graphviz *)
  val save_graphviz : t -> string -> unit
end

(** [find_model_or_generic local_model_name local_model_list] returns the model
    matching [local_model_name] from a [local_model_list] of a benchmark. If
    none match, then searches for models named ["*"]. *)
val find_model_or_generic : string -> (string * 'model) list -> 'model option

(** [load_workload_files ~local_model_name files] loads [.workload] files given in [files],
    looks for the model [local_model_name], and if found, adds it to a dependency
    graph. Returns [(G, H)] where [G] is the final graph obtained this way,
    and [H] is a table that maps the name of a benchmark with its contents. *)
val load_workload_files :
  local_model_name:string ->
  string list ->
  Graph.t * Measure.packed_measurement Namespace.Hashtbl.t