neiam /gitgud

defmodule GitGud.Workflows.Expr do
  @moduledoc """
  The slice of GitHub's expression language the forge evaluates itself.

  Almost everything in a workflow is the runner's to evaluate. The
  exception is what decides things before any runner is involved —
  `concurrency:` groups, and a job's own `if:` (`condition/2`), which
  has to be decided before the job is queued: left to the runner, a job
  whose `if:` is false but whose `runs-on` no runner carries is never
  picked up, and so never skipped. Those are nearly always built from a
  few context values: `${{ github.workflow }}-${{ github.ref }}`,
  `${{ github.event.pull_request.number || github.ref }}`,
  `${{ matrix.target }}`, `startsWith(github.ref, 'refs/tags/v')` — and
  a `strategy.matrix` computed by an earlier job, `${{
  fromJSON(needs.setup.outputs.matrix) }}`. So this covers that and no
  more:

    * property paths into `contexts` — `github.ref`, `inputs['env']`,
      `needs.build.outputs.x` — case-insensitively, as GitHub does; a path
      through something that isn't there is `null`
    * `'string'` (`''` escapes a quote), number, `true`, `false`, `null`
    * `||`, `&&` (returning an operand, not a boolean), `==`, `!=`, `<`,
      `<=`, `>`, `>=`, `!`, parentheses
    * `format('{0}-{1}', …)`, `fromJSON(string)`, `toJSON(value)`,
      `startsWith`, `endsWith`, `contains` (strings ignoring case, as
      GitHub does; `contains` also finds an element of an array)

  Anything else — another function (the status functions `success()`,
  `always()`, `failure()`, `cancelled()` among them), `*` filters, a
  context that wasn't supplied (`steps`, `env`, `secrets`, `runner`) — is
  `:error`, and the caller acts as though the expression weren't there
  rather than on a guess.

  `contexts` is a map of string-keyed maps: `%{"github" => %{…}, "matrix"
  => %{…}}`.
  """

  @typep value :: nil | boolean() | number() | String.t() | map() | list()

  @doc """
  Replace each `${{ … }}` in `string` with its value, stringified as GitHub
  does (`null` → `""`, booleans `true` / `false`). A non-string is
  stringified whole.
  """
  @spec interpolate(term(), map()) :: {:ok, String.t()} | :error
  def interpolate(string, contexts) when is_binary(string) do
    {:ok, string |> interpolate_parts(contexts, []) |> IO.iodata_to_binary()}
  catch
    :error -> :error
  end

  def interpolate(value, _contexts) when is_nil(value) or is_boolean(value) or is_number(value),
    do: {:ok, stringify(value)}

  def interpolate(_value, _contexts), do: :error

  @doc """
  The value of one expression, without the `${{ }}`.
  """
  @spec evaluate(String.t(), map()) :: {:ok, value()} | :error
  def evaluate(expression, contexts) when is_binary(expression) do
    tokens = tokenize(expression, [])

    case parse_or(tokens, contexts) do
      {value, []} -> {:ok, value}
      _ -> :error
    end
  catch
    :error -> :error
  end

  @doc """
  The value of a string that is exactly one `${{ … }}` — not stringified,
  so `${{ fromJSON('[1, 2]') }}` is a list — else `interpolate/2`'s
  string. What a workflow field that may hold an expression means.
  """
  @spec resolve(String.t(), map()) :: {:ok, value()} | :error
  def resolve(string, contexts) when is_binary(string) do
    with "${{" <> after_open <- String.trim(string),
         {expression, rest} <- take_whole_expression(after_open),
         "" <- String.trim(rest) do
      evaluate(expression, contexts)
    else
      _ -> interpolate(string, contexts)
    end
  end

  defp take_whole_expression(after_open) do
    take_expression(after_open, [])
  catch
    :error -> :error
  end

  @doc """
  What a job's `if:` decides, as a boolean: written with or without the
  `${{ }}` around it, as GitHub allows, or a YAML boolean. `:error` for
  anything that isn't one whole expression (`${{ a }} == 'b'` is a
  string to GitHub, and so always true — not what its author meant, and
  not ours to settle) or that `evaluate/2` can't evaluate.
  """
  @spec condition(term(), map()) :: {:ok, boolean()} | :error
  def condition(condition, _contexts) when is_boolean(condition), do: {:ok, condition}

  def condition(condition, contexts) when is_binary(condition) do
    with expression when is_binary(expression) <- unwrap(String.trim(condition)),
         false <- String.trim(expression) == "",
         {:ok, value} <- evaluate(expression, contexts) do
      {:ok, truthy?(value)}
    else
      _ -> :error
    end
  end

  def condition(_condition, _contexts), do: :error

  # The expression inside a `${{ }}` that is the whole string; the string
  # itself when it has none.
  defp unwrap("${{" <> after_open) do
    case take_whole_expression(after_open) do
      {expression, rest} -> if String.trim(rest) == "", do: expression, else: :error
      :error -> :error
    end
  end

  defp unwrap(string), do: if(String.contains?(string, "${{"), do: :error, else: string)

  @doc "GitHub's truthiness: `false`, `0`, `\"\"` and `null` are false."
  def truthy?(value), do: value not in [false, nil, 0, +0.0, -0.0, ""]

  # ── interpolation ───────────────────────────────────────────────────

  defp interpolate_parts(string, contexts, acc) do
    case :binary.split(string, "${{") do
      [rest] ->
        Enum.reverse([rest | acc])

      [before, after_open] ->
        {expression, rest} = take_expression(after_open, [])

        value =
          case evaluate(expression, contexts) do
            {:ok, value} -> stringify(value)
            :error -> throw(:error)
          end

        interpolate_parts(rest, contexts, [value, before | acc])
    end
  end

  # Up to the `}}` that closes the expression — not one inside a string
  # literal, which `format('{{0}}')` has.
  defp take_expression("}}" <> rest, acc),
    do: {acc |> Enum.reverse() |> IO.iodata_to_binary(), rest}

  defp take_expression("", _acc), do: throw(:error)

  defp take_expression("'" <> rest, acc) do
    {literal, rest} = take_quoted(rest, [])
    take_expression(rest, ["'", literal, "'" | acc])
  end

  defp take_expression(<<c::utf8, rest::binary>>, acc),
    do: take_expression(rest, [<<c::utf8>> | acc])

  # A quoted literal's body, `''` escapes left in, and what follows its
  # closing quote.
  defp take_quoted("''" <> rest, acc), do: take_quoted(rest, ["''" | acc])
  defp take_quoted("'" <> rest, acc), do: {acc |> Enum.reverse() |> IO.iodata_to_binary(), rest}
  defp take_quoted("", _acc), do: throw(:error)
  defp take_quoted(<<c::utf8, rest::binary>>, acc), do: take_quoted(rest, [<<c::utf8>> | acc])

  # ── tokens ──────────────────────────────────────────────────────────

  @number ~r/\A-?(?:0x[0-9a-fA-F]+|\d+(?:\.\d+)?(?:[eE][+-]?\d+)?)/
  @whole_number ~r/\A-?(?:0x[0-9a-fA-F]+|\d+(?:\.\d+)?(?:[eE][+-]?\d+)?)\z/
  @identifier ~r/\A[A-Za-z_][A-Za-z0-9_-]*/

  defp tokenize("", acc), do: Enum.reverse(acc)

  defp tokenize(<<c, rest::binary>>, acc) when c in [?\s, ?\t, ?\n, ?\r], do: tokenize(rest, acc)

  defp tokenize("||" <> rest, acc), do: tokenize(rest, [:or | acc])
  defp tokenize("&&" <> rest, acc), do: tokenize(rest, [:and | acc])
  defp tokenize("==" <> rest, acc), do: tokenize(rest, [:eq | acc])
  defp tokenize("!=" <> rest, acc), do: tokenize(rest, [:neq | acc])
  defp tokenize("<=" <> rest, acc), do: tokenize(rest, [:le | acc])
  defp tokenize(">=" <> rest, acc), do: tokenize(rest, [:ge | acc])
  defp tokenize("<" <> rest, acc), do: tokenize(rest, [:lt | acc])
  defp tokenize(">" <> rest, acc), do: tokenize(rest, [:gt | acc])
  defp tokenize("!" <> rest, acc), do: tokenize(rest, [:not | acc])
  defp tokenize("(" <> rest, acc), do: tokenize(rest, [:lparen | acc])
  defp tokenize(")" <> rest, acc), do: tokenize(rest, [:rparen | acc])
  defp tokenize("[" <> rest, acc), do: tokenize(rest, [:lbracket | acc])
  defp tokenize("]" <> rest, acc), do: tokenize(rest, [:rbracket | acc])
  defp tokenize("," <> rest, acc), do: tokenize(rest, [:comma | acc])

  defp tokenize("." <> rest, acc), do: tokenize(rest, [:dot | acc])

  defp tokenize("'" <> rest, acc) do
    {body, rest} = take_quoted(rest, [])
    tokenize(rest, [{:literal, String.replace(body, "''", "'")} | acc])
  end

  defp tokenize(string, acc) do
    cond do
      match = Regex.run(@number, string) ->
        [text] = match
        tokenize(binary_part_after(string, text), [{:literal, parse_number(text)} | acc])

      match = Regex.run(@identifier, string) ->
        [text] = match
        tokenize(binary_part_after(string, text), [identifier(text) | acc])

      true ->
        throw(:error)
    end
  end

  defp binary_part_after(string, prefix),
    do: binary_part(string, byte_size(prefix), byte_size(string) - byte_size(prefix))

  defp identifier("true"), do: {:literal, true}
  defp identifier("false"), do: {:literal, false}
  defp identifier("null"), do: {:literal, nil}
  defp identifier(name), do: {:name, name}

  defp parse_number(text) do
    {sign, digits} =
      case text do
        "-" <> digits -> {-1, digits}
        digits -> {1, digits}
      end

    cond do
      String.starts_with?(digits, "0x") ->
        sign * String.to_integer(binary_part_after(digits, "0x"), 16)

      String.contains?(digits, [".", "e", "E"]) ->
        {float, ""} = Float.parse(digits)
        sign * float

      true ->
        sign * String.to_integer(digits)
    end
  end

  # ── parser (evaluating as it goes: nothing here has side effects) ──

  defp parse_or(tokens, contexts) do
    {left, rest} = parse_and(tokens, contexts)
    parse_or_rest(left, rest, contexts)
  end

  defp parse_or_rest(left, [:or | rest], contexts) do
    {right, rest} = parse_and(rest, contexts)
    parse_or_rest(if(truthy?(left), do: left, else: right), rest, contexts)
  end

  defp parse_or_rest(left, rest, _contexts), do: {left, rest}

  defp parse_and(tokens, contexts) do
    {left, rest} = parse_equality(tokens, contexts)
    parse_and_rest(left, rest, contexts)
  end

  defp parse_and_rest(left, [:and | rest], contexts) do
    {right, rest} = parse_equality(rest, contexts)
    parse_and_rest(if(truthy?(left), do: right, else: left), rest, contexts)
  end

  defp parse_and_rest(left, rest, _contexts), do: {left, rest}

  defp parse_equality(tokens, contexts) do
    {left, rest} = parse_comparison(tokens, contexts)
    parse_equality_rest(left, rest, contexts)
  end

  defp parse_equality_rest(left, [op | rest], contexts) when op in [:eq, :neq] do
    {right, rest} = parse_comparison(rest, contexts)
    equal = equal?(left, right)
    parse_equality_rest(if(op == :eq, do: equal, else: not equal), rest, contexts)
  end

  defp parse_equality_rest(left, rest, _contexts), do: {left, rest}

  # `<` and friends bind tighter than `==`, as in GitHub's grammar.
  defp parse_comparison(tokens, contexts) do
    {left, rest} = parse_unary(tokens, contexts)
    parse_comparison_rest(left, rest, contexts)
  end

  defp parse_comparison_rest(left, [op | rest], contexts) when op in [:lt, :le, :gt, :ge] do
    {right, rest} = parse_unary(rest, contexts)
    parse_comparison_rest(compare(op, left, right), rest, contexts)
  end

  defp parse_comparison_rest(left, rest, _contexts), do: {left, rest}

  defp parse_unary([:not | rest], contexts) do
    {value, rest} = parse_unary(rest, contexts)
    {not truthy?(value), rest}
  end

  defp parse_unary(tokens, contexts) do
    {value, rest} = parse_primary(tokens, contexts)
    parse_postfix(value, rest, contexts)
  end

  defp parse_postfix(value, [:dot, {:name, key} | rest], contexts),
    do: parse_postfix(property(value, key), rest, contexts)

  # `github.event.true` is a property named `true`, however it tokenized.
  defp parse_postfix(value, [:dot, {:literal, key} | rest], contexts)
       when is_boolean(key) or is_nil(key),
       do: parse_postfix(property(value, to_string(key)), rest, contexts)

  defp parse_postfix(value, [:lbracket | rest], contexts) do
    case parse_or(rest, contexts) do
      {index, [:rbracket | rest]} -> parse_postfix(property(value, index), rest, contexts)
      _ -> throw(:error)
    end
  end

  defp parse_postfix(_value, [:dot | _], _contexts), do: throw(:error)
  defp parse_postfix(value, rest, _contexts), do: {value, rest}

  defp parse_primary([{:literal, value} | rest], _contexts), do: {value, rest}

  defp parse_primary([:lparen | rest], contexts) do
    case parse_or(rest, contexts) do
      {value, [:rparen | rest]} -> {value, rest}
      _ -> throw(:error)
    end
  end

  defp parse_primary([{:name, name}, :lparen | rest], contexts) do
    {args, rest} = parse_args(rest, contexts, [])
    {call(String.downcase(name), args), rest}
  end

  defp parse_primary([{:name, name} | rest], contexts) do
    case lookup(contexts, name) do
      {:ok, value} -> {value, rest}
      :error -> throw(:error)
    end
  end

  defp parse_primary(_tokens, _contexts), do: throw(:error)

  defp parse_args([:rparen | rest], _contexts, []), do: {[], rest}

  defp parse_args(tokens, contexts, acc) do
    case parse_or(tokens, contexts) do
      {value, [:comma | rest]} -> parse_args(rest, contexts, [value | acc])
      {value, [:rparen | rest]} -> {Enum.reverse([value | acc]), rest}
      _ -> throw(:error)
    end
  end

  # ── semantics ───────────────────────────────────────────────────────

  defp call("format", [template | args]) when is_binary(template),
    do: format(template, Enum.map(args, &stringify/1), [])

  defp call("fromjson", [json]) when is_binary(json) do
    case Jason.decode(json) do
      {:ok, value} -> value
      {:error, _} -> throw(:error)
    end
  end

  defp call("tojson", [value]), do: Jason.encode!(value, pretty: true)

  # GitHub casts both sides to strings and ignores case.
  defp call("startswith", [string, prefix]),
    do: String.starts_with?(fold(string), fold(prefix))

  defp call("endswith", [string, suffix]),
    do: String.ends_with?(fold(string), fold(suffix))

  # An array holds the item when an element equals it (loosely, as
  # `==`); anything else is searched as a string.
  defp call("contains", [list, item]) when is_list(list),
    do: Enum.any?(list, &equal?(&1, item))

  defp call("contains", [string, item]), do: String.contains?(fold(string), fold(item))

  defp call(_function, _args), do: throw(:error)

  defp format("", _args, acc), do: acc |> Enum.reverse() |> IO.iodata_to_binary()
  defp format("{{" <> rest, args, acc), do: format(rest, args, ["{" | acc])
  defp format("}}" <> rest, args, acc), do: format(rest, args, ["}" | acc])

  defp format("{" <> rest, args, acc) do
    with [digits, rest] <- :binary.split(rest, "}"),
         {index, ""} <- Integer.parse(digits),
         true <- index >= 0 and index < length(args) do
      format(rest, args, [Enum.at(args, index) | acc])
    else
      _ -> throw(:error)
    end
  end

  defp format("}" <> _rest, _args, _acc), do: throw(:error)
  defp format(<<c::utf8, rest::binary>>, args, acc), do: format(rest, args, [<<c::utf8>> | acc])

  # Top-level names are contexts; a name nobody supplied is an error, not
  # null, because it means the expression reads something we don't model.
  defp lookup(contexts, name), do: find_key(contexts, name)

  defp property(%{} = map, key) when is_binary(key) do
    case find_key(map, key) do
      {:ok, value} -> value
      :error -> nil
    end
  end

  defp property(%{} = map, key) when is_number(key), do: property(map, stringify(key))

  defp property(list, index) when is_list(list) and is_number(index) and index >= 0 do
    if index == trunc(index), do: Enum.at(list, trunc(index)), else: nil
  end

  defp property(_value, _key), do: nil

  defp find_key(map, key) do
    case Map.fetch(map, key) do
      {:ok, value} ->
        {:ok, value}

      :error ->
        down = String.downcase(key)

        Enum.find_value(map, :error, fn {k, v} ->
          is_binary(k) and String.downcase(k) == down and {:ok, v}
        end)
    end
  end

  # GitHub's loose equality: same type compares directly (strings ignoring
  # case); different types compare as numbers, where anything that isn't
  # one is NaN and equals nothing.
  defp equal?(a, b) when is_binary(a) and is_binary(b),
    do: String.downcase(a) == String.downcase(b)

  defp equal?(a, b) when is_number(a) and is_number(b), do: a == b
  defp equal?(a, b) when is_boolean(a) and is_boolean(b), do: a == b
  defp equal?(nil, nil), do: true
  defp equal?(a, b) when is_map(a) or is_list(a) or is_map(b) or is_list(b), do: a === b

  defp equal?(a, b) do
    case {to_number(a), to_number(b)} do
      {x, y} when is_number(x) and is_number(y) -> x == y
      _ -> false
    end
  end

  # GitHub's ordering: two strings compare ignoring case; anything else
  # compares as numbers, and NaN is neither less nor greater than
  # anything.
  defp compare(op, a, b) when is_binary(a) and is_binary(b),
    do: ordered?(op, String.downcase(a), String.downcase(b))

  defp compare(_op, a, b) when is_map(a) or is_list(a) or is_map(b) or is_list(b), do: false

  defp compare(op, a, b) do
    case {to_number(a), to_number(b)} do
      {x, y} when is_number(x) and is_number(y) -> ordered?(op, x, y)
      _ -> false
    end
  end

  defp ordered?(:lt, a, b), do: a < b
  defp ordered?(:le, a, b), do: a <= b
  defp ordered?(:gt, a, b), do: a > b
  defp ordered?(:ge, a, b), do: a >= b

  defp fold(value), do: value |> stringify() |> String.downcase()

  defp to_number(nil), do: 0
  defp to_number(true), do: 1
  defp to_number(false), do: 0
  defp to_number(n) when is_number(n), do: n

  defp to_number(s) when is_binary(s) do
    case String.trim(s) do
      "" ->
        0

      trimmed ->
        if Regex.match?(@whole_number, trimmed), do: parse_number(trimmed), else: :nan
    end
  end

  defp to_number(_), do: :nan

  defp stringify(nil), do: ""
  defp stringify(true), do: "true"
  defp stringify(false), do: "false"
  defp stringify(s) when is_binary(s), do: s
  defp stringify(n) when is_integer(n), do: Integer.to_string(n)

  defp stringify(n) when is_float(n) do
    if n == trunc(n) and abs(n) < 1.0e15,
      do: Integer.to_string(trunc(n)),
      else: Float.to_string(n)
  end

  # GitHub would print an object as JSON; a concurrency group made of one
  # is a mistake, and saying so beats a group nobody can read.
  defp stringify(_object), do: throw(:error)
end