grains

defmodule Grains.Bread do
  @moduledoc """
  A `%Bread{}` is the compiled version of Recipe plus Grains
  that allow the Supervisor to
  run the processes and wire them correctly.
  """
  alias Grains.Recipe

  @type t :: %__MODULE__{}

  defstruct [
    :id,
    :original_recipe,
    :original_grains,
    :child_specs,
    :final_recipe,
    :sup,
    :name,
    :final_grains,
    :routes,
    :process_map
  ]

  @doc """
  Takes a recipe, grains and optionally a map of default implementations
  and returns a bread. Does not start any processes yet.

  ## Optional Arguments

  * `:id` Set a custom bread id

  """
  def bake(recipe = %Recipe{}, grains = %Grains{}, args \\ []) do
    id = args[:id] || gen_id()

    name = Grains.make_bread_name(recipe, id)

    prebread = %__MODULE__{
      id: id,
      original_recipe: recipe,
      original_grains: grains,
      routes: %{},
      name: name
    }

    prebread
    |> unfold()
    |> process_map()
    |> child_specs()
  end

  # Function takes a half done (pre)-bread to
  # - fill in the edges in the graph that are needed for build in
  # functionality, like the periodic timer.
  defp unfold(prebread = %{original_grains: grains}) do
    ctx = Map.from_struct(prebread)

    %{addional_grains: addional_grains, edges: edges} =
      prebread.original_recipe.map
      |> Enum.map(&unfold1(ctx, &1))
      |> merge_maps(tree(%{}))
      |> squash()

    addional_grains = addional_grains |> Enum.into(%{})
    final_grains = %Grains{grains | map: Map.merge(grains.map, addional_grains)}
    %__MODULE__{prebread | final_grains: final_grains, final_recipe: edges}
  end

  defp unfold1(_ctx, {left, right}) when is_atom(right) do
    edge = {left, right, %{}}
    %{edges: [edge]} |> tree()
  end

  defp unfold1(ctx, {left, right}) when is_list(right) do
    right
    |> Enum.map(&unfold1(ctx, {left, &1}))
    |> merge_maps()
  end

  defp unfold1(ctx, {left, {:route, router, right, string}}) do
    right
    |> List.wrap()
    |> Enum.map(&unfold1(ctx, {left, &1}))
    |> Enum.map(fn l ->
      f = fn {l, r, m} -> {l, r, merge_maps(m, %{router: [router], router_string: [string]})} end
      update_in(l.edges, &Enum.map(&1, f))
    end)
    |> merge_maps()
  end

  defp unfold1(%{in_periodic: True}, {_left, {:periodic, _right, _args}}) do
    raise "Nested periodic is not allowed."
  end

  defp unfold1(ctx, {left, {:periodic, right, args}}) do
    # this prevents nested periodic, because periodic makes
    # names depend on left and right
    inner_ctx = Map.put(ctx, :in_periodic, True)

    right_names =
      right
      |> List.wrap()
      |> Enum.map(fn r -> unfold1(inner_ctx, {:timer, r}) end)
      |> merge_maps()
      |> Map.get(:edges, [])
      |> Enum.filter(fn {l, _, _} -> l == :timer end)
      |> Enum.map(fn {_, r, _} -> r end)
      |> Enum.uniq()

    timer = Grains.Timer.name(left, right_names)
    {impl, add_args, opts} = Map.get(ctx.original_grains.map, timer, {Grains.Timer, [], []})

    args = Enum.into(add_args, args)

    leaves =
      right
      |> List.wrap()
      |> Enum.map(fn r ->
        unfold1(ctx, {timer, r})
      end)

    [
      unfold1(ctx, {left, timer}),
      %{leaves: leaves, addional_grains: [{timer, {impl, args, opts}}]}
    ]
    |> merge_maps()
  end

  defp unfold1(_ctx, {_left, {:ghost, _ghost, _description}}) do
    tree(%{})
  end

  defp tree(map) do
    defaults = %{edges: [], addional_grains: [], leaves: []}
    merge_maps([defaults, map])
  end

  defp squash(m = %{leaves: []}) do
    m
  end

  defp squash(m = %{leaves: leaves}) do
    m
    |> Map.delete(:leaves)
    |> merge_maps(leaves)
    |> squash()
  end

  # Builds a mapping from short names to process names.
  defp process_map(prebread = %{final_grains: grains, id: bread_id, original_recipe: recipe}) do
    Enum.map(grains.map, fn {short_name, _} ->
      process_name = Grains.make_name(recipe, bread_id, short_name)
      {short_name, process_name}
    end)
    |> Enum.into(%{})
    |> (&%__MODULE__{prebread | process_map: &1}).()
  end

  @doc """
  Generates a random atom to be used as an id for the Bread
  """
  def gen_id do
    8
    |> :crypto.strong_rand_bytes()
    |> Base.encode32(padding: false)
    |> String.to_atom()
  end

  defp child_specs(bread = %__MODULE__{final_grains: grains, process_map: process_map}) do
    Enum.map(grains.map, fn {short_name, {module, args, opts}} ->
      process_name = Map.fetch!(process_map, short_name)

      %{
        id: process_name,
        start:
          {Grains.GenGrain, :start_link,
           [module, bread, short_name, args, [name: process_name || opts]]}
      }
    end)
    |> (&%__MODULE__{bread | child_specs: &1}).()
  end

  defp merge_maps(a, b), do: merge_maps([a, b])

  defp merge_maps(routes) when is_list(routes) do
    routes
    |> List.flatten()
    |> Enum.reduce(%{}, &Map.merge(&1, &2, fn _, v1, v2 -> v1 ++ v2 end))
  end

  def check(%__MODULE__{process_map: processes_map, final_recipe: final_recipe}) do
    grain_short_names = Map.keys(processes_map)

    recipe_names =
      final_recipe
      |> Enum.flat_map(fn {l, r, _att} -> [l, r] end)
      |> Enum.uniq()

    test = fn x ->
      Enum.member?(grain_short_names, x) or
        x |> Module.split() |> Enum.drop(1) |> List.first() == "Timer"
    end

    case Enum.reject(recipe_names, test) do
      [] ->
        :ok

      gs ->
        {:error, {:missing_grain, gs}}
    end
  end

  @doc """
  Retrieve all successors of `short_name`.
  """
  def successors(%__MODULE__{final_recipe: final_recipe}, short_name) do
    final_recipe
    |> Enum.filter(fn {l, _, _att} -> l == short_name end)
    |> Enum.map(fn
      {_, r, _att} when is_atom(r) -> r
    end)
  end

  @doc """
  Retrieve all predecessors of `short_name`.
  """
  def predecessors(%__MODULE__{final_recipe: final_recipe}, short_name) do
    final_recipe
    |> Enum.filter(fn
      {_, r, _att} when is_atom(r) -> r == short_name
    end)
    |> Enum.map(fn {l, _, _att} -> l end)
  end

  @doc """
  Retrieve all routes of `short_name`.
  """
  def routes(%__MODULE__{final_recipe: final_recipe}, short_name) do
    Enum.flat_map(final_recipe, fn
      {^short_name, right, %{router: router}} -> [{right, router}]
      _ -> []
    end)
  end

  @doc """
  Retrieve all cycle-free paths between `first` and `last`.
  """
  def paths_between(bread = %__MODULE__{}, first, last) do
    Bread.Graph.all_paths(bread, first, last, &successors/2)
  end

  @doc """
  Retrieve all cycle-free pull-paths between `first` and `last`.
  """
  def pull_paths_between(bread = %__MODULE__{}, first, last) do
    Bread.Graph.all_paths(bread, first, last, &predecessors/2)
  end
end

defmodule Bread.Graph.Path do
  @moduledoc false
  defstruct path: [], visited: MapSet.new()

  def new do
    %__MODULE__{}
  end

  def visited?(path, vertex) do
    vertex in path.visited
  end

  def add(path, vertex) do
    false = visited?(path, vertex)
    %__MODULE__{path | path: [vertex | path.path], visited: MapSet.put(path.visited, vertex)}
  end
end

defmodule Bread.Graph do
  @moduledoc false

  alias Bread.Graph.Path

  def all_paths(graph, start, target, adjacent) when is_function(adjacent, 2) do
    initial_path = Path.new() |> Path.add(start)

    all_paths1(graph, adjacent, :queue.from_list([initial_path]), target, [])
  end

  defp all_paths1(graph, adjacent, q, target, all_paths_to_target) do
    case :queue.out(q) do
      {:empty, _} ->
        all_paths_to_target
        |> Enum.map(& &1.path)
        |> Enum.map(&Enum.reverse/1)

      {{:value, path}, q} ->
        [top | _] = path.path

        if top == target do
          all_paths1(graph, adjacent, q, target, [path | all_paths_to_target])
        else
          adjacent_vertices = adjacent.(graph, top) || []

          q =
            Enum.reduce(adjacent_vertices, q, fn vertex, q ->
              if Path.visited?(path, vertex) do
                q
              else
                path
                |> Path.add(vertex)
                |> :queue.in(q)
              end
            end)

          all_paths1(graph, adjacent, q, target, all_paths_to_target)
        end
    end
  end
end