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
    queue = :queue.from_list([first])
    paths = %{first => [[]]}
    visited = MapSet.new()

    paths = find_all_paths(bread, queue, visited, paths)

    if matching = paths[last] do
      Enum.map(matching, &Enum.reverse([last | &1]))
    else
      []
    end
  end

  # Breadth-first traversal of the graph. A node is visited at most once.
  defp find_all_paths(bread, queue, visited, paths) do
    case :queue.out(queue) do
      {{:value, current}, queue} ->
        if current in visited do
          find_all_paths(bread, queue, visited, paths)
        else
          visited = MapSet.put(visited, current)

          unexpanded_successors =
            bread
            |> successors(current)
            |> MapSet.new()
            |> MapSet.difference(visited)

          queue = Enum.reduce(unexpanded_successors, queue, &:queue.in/2)

          paths_to_current = Map.get(paths, current, [[]])
          paths_through_current = Enum.map(paths_to_current, &[current | &1])

          paths =
            Enum.reduce(unexpanded_successors, paths, fn succ, paths ->
              Map.put(paths, succ, Map.get(paths, succ, []) ++ paths_through_current)
            end)

          find_all_paths(bread, queue, visited, paths)
        end

      {:empty, _} ->
        paths
    end
  end
end