neiam /gitgud

defmodule GitGud.Workflows.Matrix do
  @moduledoc """
  Expands a job's `strategy.matrix` into the combinations it stands for.

      strategy:
        matrix:
          arch: [amd64, arm64]
          otp: ["27", "28"]

  …is four jobs. Each becomes its own `WorkflowJob` row, with its own
  status, logs and runner — which is the point: two of those want an
  amd64 machine and two want arm64, and only separate rows can be
  claimed by separate runners.

  ## `include` and `exclude`

  Both are ordinary GitHub Actions semantics and both are fiddly, so
  they are spelled out here rather than left to the reader:

    * `exclude` drops every combination that matches *all* of the
      key/values it names. It is applied before `include`, so an
      `include` can add a combination back.

    * `include` is not "append these combinations". Each entry is
      merged into every existing combination whose overlapping keys
      already agree with it — so `{otp: "28", coverage: true}` adds
      `coverage` to the two OTP-28 jobs rather than creating a fifth.
      An entry that matches nothing is appended as a combination of its
      own, which is how you add a single odd platform to a matrix.

  An entry that *would* overwrite a value the base matrix set is where
  GitHub's own rules get genuinely ambiguous; here, overlapping keys
  must agree for a merge to happen, so such an entry appends instead.

  ## Ordering

  Combinations come back in the order GitHub produces them: the *last*
  matrix key varies fastest. That is only cosmetic, but it decides the
  order jobs appear in the UI, and matching the tool people already
  know beats an arbitrary choice.
  """

  alias GitGud.Workflows.Expr

  @reserved ~w(include exclude)

  @typedoc "One combination: matrix key to the value this leg was expanded for."
  @type combination :: %{String.t() => term()}

  @doc """
  Every combination `strategy` expands to, as `{:ok, combinations}`.

  Returns `{:ok, [%{}]}` — a single empty combination — when there is no
  matrix (or one with no axes and no `include`), so callers can treat
  "no matrix" as "one leg with nothing in it" rather than branching.

  Expressions are resolved first, against `contexts` (`GitGud.Workflows.Expr`):
  the whole matrix (`matrix: ${{ fromJSON(needs.setup.outputs.matrix) }}`,
  which must yield an object), an axis or an `include` / `exclude`
  (which must yield an array), an entry of those (an object), or a value.

  `{:error, reason}` when an expression can't be evaluated or yields the
  wrong shape, or — as on GitHub, where it fails the workflow — when
  `exclude` leaves nothing (`:empty_matrix`). `describe_error/1` words it.
  """
  @spec expand(map() | nil, map()) :: {:ok, [combination()]} | {:error, term()}
  def expand(strategy, contexts \\ %{})

  def expand(%{"matrix" => matrix}, contexts) when is_binary(matrix) or is_map(matrix) do
    with {:ok, matrix} <- resolve_matrix(matrix, contexts),
         {:ok, axes} <- resolve_axes(matrix, contexts),
         {:ok, exclusions} <- resolve_entries(matrix, "exclude", contexts),
         {:ok, inclusions} <- resolve_entries(matrix, "include", contexts) do
      if axes == [] and inclusions == [] do
        {:ok, [%{}]}
      else
        axes
        |> product()
        |> exclude(exclusions)
        |> include(inclusions)
        |> case do
          [] -> {:error, :empty_matrix}
          combinations -> {:ok, combinations}
        end
      end
    end
  end

  def expand(_strategy, _contexts), do: {:ok, [%{}]}

  @doc "The log line for an `expand/2` error."
  @spec describe_error(term()) :: String.t()
  def describe_error(:empty_matrix),
    do: "The matrix has no combinations: exclude removed every one, or an axis is empty."

  def describe_error({:expression, text}),
    do: "The matrix expression #{text} could not be evaluated."

  def describe_error({:not_object, what}), do: "The matrix #{what} is not an object."
  def describe_error({:not_list, what}), do: "The matrix #{what} is not an array."

  @doc """
  Whether `strategy` asks for a matrix at all.

  A `strategy:` with only `fail-fast:` on it is not a matrix, and its
  job should not be renamed as though it were one leg of something. A
  matrix that is an expression is one, whatever it turns out to hold.
  """
  @spec matrix?(map() | nil) :: boolean()
  def matrix?(%{"matrix" => %{} = matrix}), do: matrix != %{}
  def matrix?(%{"matrix" => matrix}) when is_binary(matrix), do: true
  def matrix?(_), do: false

  @doc """
  Whether the matrix holds an expression anywhere — so it can only be
  expanded once its contexts exist (`needs`, when it reads them).
  """
  @spec dynamic?(map() | nil) :: boolean()
  def dynamic?(%{"matrix" => matrix}), do: expression?(matrix)
  def dynamic?(_), do: false

  defp expression?(value) when is_binary(value), do: String.contains?(value, "${{")
  defp expression?(%{} = map), do: Enum.any?(map, fn {_key, value} -> expression?(value) end)
  defp expression?(list) when is_list(list), do: Enum.any?(list, &expression?/1)
  defp expression?(_value), do: false

  @doc """
  `strategy.max-parallel`: how many legs of the job may run at once, or
  nil for no limit. A positive integer (or its digits as a string, which
  is how a quoted YAML value arrives); anything else, an expression
  included, is no limit. Claiming reads the same rule in SQL
  (`Workflows.do_claim_next_job/3`).
  """
  @spec max_parallel(map() | nil) :: pos_integer() | nil
  def max_parallel(%{"max-parallel" => n}) when is_integer(n) and n > 0, do: n

  def max_parallel(%{"max-parallel" => n}) when is_binary(n) do
    if Regex.match?(~r/\A[1-9][0-9]{0,8}\z/, n), do: String.to_integer(n)
  end

  def max_parallel(_strategy), do: nil

  @doc """
  Whether a failing leg should cancel its siblings. GitHub's default is
  `true`, and so is ours.
  """
  @spec fail_fast?(map() | nil) :: boolean()
  def fail_fast?(%{"fail-fast" => false}), do: false
  def fail_fast?(%{"fail-fast" => "false"}), do: false
  def fail_fast?(_), do: true

  @doc """
  The display suffix GitHub puts on a matrix leg — `build (arm64, 28)`.

  Values in the order their keys sort, which is the order `expand/1`
  varied them, so reading two names side by side tells you which axis
  differs.
  """
  @spec suffix(combination()) :: String.t() | nil
  def suffix(combination) when map_size(combination) == 0, do: nil

  def suffix(combination) do
    combination
    |> Enum.sort_by(&elem(&1, 0))
    |> Enum.map_join(", ", fn {_key, value} -> to_string(value) end)
  end

  @doc """
  Substitute `${{ matrix.key }}` in a `runs-on` value.

  Only `runs-on` needs this. Everything else the runner evaluates for
  itself — see `GitGud.Workflows.RunnerPayload`, which hands `act` a
  one-value matrix so the whole `matrix` context resolves natively.
  But routing is *our* decision and happens before any runner sees the
  job, so this one expression has to be resolved server-side.

  An unknown key resolves to the empty string, as it does in Actions.
  """
  @spec substitute(term(), combination()) :: term()
  def substitute(value, combination) when is_list(value),
    do: Enum.map(value, &substitute(&1, combination))

  def substitute(value, combination) when is_binary(value) do
    Regex.replace(~r/\$\{\{\s*matrix\.([A-Za-z_][A-Za-z0-9_-]*)\s*\}\}/, value, fn _, key ->
      combination |> Map.get(key, "") |> to_string()
    end)
  end

  def substitute(value, _combination), do: value

  @doc """
  Normalise a `runs-on` into the list of labels a runner must carry.

  `runs-on: ubuntu-latest` and `runs-on: [ubuntu-latest]` mean the same
  thing and are stored the same way, so claiming has one shape to match
  rather than two.
  """
  @spec labels(term()) :: [String.t()]
  def labels(runs_on) do
    runs_on
    |> List.wrap()
    |> Enum.map(&to_string/1)
    |> Enum.reject(&(&1 == ""))
    |> Enum.uniq()
  end

  @doc """
  Rewrite a job definition so it describes exactly this one leg.

  The matrix is replaced by the single combination rather than
  removed: `act` then expands it to exactly one job and populates the
  `matrix` context from it, so `${{ matrix.arch }}` inside a step keeps
  working without us implementing an expression evaluator. Dropping
  `strategy` entirely would leave those expressions resolving to
  nothing; leaving it whole would have the runner fan out *again*,
  inside the single job we just handed it.
  """
  @spec pin_definition(map(), combination()) :: map()
  def pin_definition(definition, combination) when map_size(combination) == 0,
    do: Map.drop(definition, ["strategy"])

  def pin_definition(definition, combination) do
    pinned = Map.new(combination, fn {key, value} -> {key, [value]} end)
    strategy = Map.get(definition, "strategy") || %{}

    # `fail-fast` and `max-parallel` ride along even though they mean
    # nothing to a one-value matrix: the forge reads them back off the
    # stored definition — to decide whether a failing leg cancels its
    # siblings, and how many legs may be claimed at once — and the
    # pinned strategy is the only copy that survives.
    kept =
      strategy
      |> Map.take(["fail-fast", "max-parallel"])
      |> Map.put("matrix", pinned)

    Map.put(definition, "strategy", kept)
  end

  # ── expansion internals ─────────────────────────────────────────────

  # The matrix itself as a map: an expression must yield one.
  defp resolve_matrix(matrix, contexts) when is_binary(matrix) do
    case evaluate(matrix, contexts) do
      {:ok, %{} = resolved} -> {:ok, resolved}
      {:ok, _other} -> {:error, {:not_object, matrix}}
      error -> error
    end
  end

  defp resolve_matrix(matrix, _contexts), do: {:ok, matrix}

  # `[{key, values}]`, sorted. An axis that is an expression must yield
  # an array; a literal scalar is a one-value axis, as it always was.
  defp resolve_axes(matrix, contexts) do
    matrix
    |> Map.drop(@reserved)
    # Map iteration order is undefined; sort so a given workflow always
    # expands the same way rather than shuffling between deploys.
    |> Enum.sort_by(&elem(&1, 0))
    |> map_ok(fn {key, values} ->
      case resolve_value(values, contexts) do
        {:ok, list} when is_list(list) -> {:ok, {key, list}}
        {:ok, _other} when is_binary(values) -> not_list(values, key)
        {:ok, other} -> {:ok, {key, List.wrap(other)}}
        error -> error
      end
    end)
  end

  defp not_list(values, key) do
    if expression?(values),
      do: {:error, {:not_list, "axis #{key}"}},
      else: {:ok, {key, [values]}}
  end

  # `include` / `exclude`: a list of objects, each of which (or the whole
  # list) may be an expression.
  defp resolve_entries(matrix, key, contexts) do
    with {:ok, entries} <- resolve_value(Map.get(matrix, key), contexts) do
      entries
      |> List.wrap()
      |> map_ok(fn
        %{} = entry -> {:ok, Map.new(entry, fn {k, v} -> {to_string(k), v} end)}
        _other -> {:error, {:not_object, "#{key} entry"}}
      end)
    end
  end

  defp resolve_value(value, contexts) when is_binary(value) do
    if String.contains?(value, "${{"), do: evaluate(value, contexts), else: {:ok, value}
  end

  defp resolve_value(%{} = map, contexts) do
    with {:ok, pairs} <-
           map_ok(map, fn {key, value} ->
             with {:ok, value} <- resolve_value(value, contexts), do: {:ok, {key, value}}
           end),
         do: {:ok, Map.new(pairs)}
  end

  defp resolve_value(list, contexts) when is_list(list),
    do: map_ok(list, &resolve_value(&1, contexts))

  defp resolve_value(value, _contexts), do: {:ok, value}

  defp evaluate(text, contexts) do
    case Expr.resolve(text, contexts) do
      {:ok, value} -> {:ok, value}
      :error -> {:error, {:expression, text}}
    end
  end

  defp map_ok(enumerable, fun) do
    Enum.reduce_while(enumerable, {:ok, []}, fn item, {:ok, acc} ->
      case fun.(item) do
        {:ok, value} -> {:cont, {:ok, [value | acc]}}
        error -> {:halt, error}
      end
    end)
    |> case do
      {:ok, acc} -> {:ok, Enum.reverse(acc)}
      error -> error
    end
  end

  # Cartesian product with the last axis varying fastest, matching the
  # order Actions lists a matrix's jobs in.
  defp product([]), do: []

  defp product(axes) do
    Enum.reduce(axes, [%{}], fn {key, values}, acc ->
      for combination <- acc, value <- values, do: Map.put(combination, key, value)
    end)
  end

  defp exclude(combinations, []), do: combinations

  defp exclude(combinations, exclusions) do
    Enum.reject(combinations, fn combination ->
      Enum.any?(exclusions, &subset_of?(&1, combination))
    end)
  end

  defp include(combinations, []), do: combinations

  defp include(combinations, inclusions) do
    Enum.reduce(inclusions, combinations, fn entry, acc ->
      merged = Enum.map(acc, &merge_if_compatible(&1, entry))

      # Nothing took it — it describes a combination of its own.
      if merged == acc, do: acc ++ [entry], else: merged
    end)
  end

  # Compatible means every key they share already agrees. An entry that
  # would change an existing value describes a different combination,
  # not an addition to this one.
  defp merge_if_compatible(combination, entry) do
    overlapping = Map.take(entry, Map.keys(combination))

    if subset_of?(overlapping, combination) and entry != overlapping,
      do: Map.merge(combination, entry),
      else: combination
  end

  defp subset_of?(subset, combination) do
    Enum.all?(subset, fn {key, value} ->
      Map.has_key?(combination, key) and to_string(Map.get(combination, key)) == to_string(value)
    end)
  end
end