neiam /gitgud

defmodule GitGud.Workflows.Glob do
  @moduledoc """
  Filter patterns as workflows write them under `branches:`, `tags:`,
  `paths:` and their `-ignore` lists, with GitHub's rules (its "filter
  pattern cheat sheet"), because that is the documentation the patterns
  are copied from:

    * `*` matches any run of characters except `/`
    * `**` matches any run of characters including `/`; `**/` also matches
      no directory at all, so `**/*.md` matches `README.md`
    * `?` makes the preceding character (or class) optional, `+` repeats
      it one or more times — regex quantifiers, not wildcards. At the start
      of a pattern, or after `*`, `**` or another quantifier, they are
      literal
    * `[abc]`, `[a-z]` match one character listed or in a range; only
      alphanumerics and ranges within `a-z`, `A-Z`, `0-9`. Anything else
      in the brackets (`[!a]`, `[^a]`, `[.]`) makes the `[` literal
    * `\\x` is a literal `x` (`\\*`, `\\[`, `\\!`)
    * everything else is literal — `.` is a dot

  Patterns are anchored at both ends. A leading `!` negates, and means
  something only in a list: see `select?/2`.

  Not used for branch protection or required checks, whose `*` crosses `/`
  (`GitGud.BranchProtections`).
  """

  import Kernel, except: [match?: 2]

  require Logger

  @typedoc "A list compiled by `compile_list/1`: `{positive?, regex}` in order."
  @type rules :: [{boolean(), Regex.t()}]

  @doc """
  Compile `pattern` into an anchored regex.

      iex> Regex.source(GitGud.Workflows.Glob.compile("docs/*.md"))
      "^docs/[^/]*\\\\.md$"
  """
  @spec compile(String.t()) :: Regex.t()
  def compile(pattern) when is_binary(pattern) do
    Regex.compile!("^" <> render(translate(pattern, [])) <> "$")
  end

  @doc """
  Whether `string` matches `pattern` (a string, or a regex from `compile/1`).

      iex> GitGud.Workflows.Glob.match?("**/*.md", "README.md")
      true
  """
  @spec match?(String.t() | Regex.t(), String.t()) :: boolean()
  def match?(%Regex{} = regex, string) when is_binary(string), do: Regex.match?(regex, string)
  def match?(pattern, string) when is_binary(pattern), do: Regex.match?(compile(pattern), string)

  @doc """
  Compile a list of patterns for `select?/2`, so a list checked against
  many strings (a push's changed files) is compiled once. A list with no
  positive pattern selects nothing — GitHub rejects it — and is logged.
  """
  @spec compile_list([String.t()]) :: rules()
  def compile_list(patterns) when is_list(patterns) do
    rules =
      Enum.map(patterns, fn
        "!" <> pattern -> {false, compile(pattern)}
        pattern -> {true, compile(pattern)}
      end)

    if rules != [] and not Enum.any?(rules, &elem(&1, 0)) do
      Logger.warning(
        "filter #{inspect(patterns)} has only negative patterns, so it matches nothing"
      )
    end

    rules
  end

  @doc """
  Whether a list of patterns selects `string`: the **last** pattern that
  matches decides, `!pattern` deselecting and a later positive pattern
  selecting again. Nothing matching, or no positive pattern at all, is
  `false`. Takes patterns or a list from `compile_list/1`.

      iex> GitGud.Workflows.Glob.select?(["*", "!b*", "beta"], "beta")
      true
      iex> GitGud.Workflows.Glob.select?(["*", "!b*", "beta"], "bravo")
      false
  """
  @spec select?([String.t()] | rules(), String.t()) :: boolean()
  def select?([{positive?, %Regex{}} | _] = rules, string) when is_boolean(positive?) do
    Enum.reduce(rules, false, fn {positive?, regex}, selected? ->
      if Regex.match?(regex, string), do: positive?, else: selected?
    end)
  end

  def select?([], _string), do: false

  def select?(patterns, string) when is_list(patterns),
    do: select?(compile_list(patterns), string)

  # The pattern becomes a list of atoms, most recent first, so a `?` or `+`
  # can see what it follows:
  #
  #   {:lit, char} | {:class, body} | {:quant, atom, "?" | "+"}
  #   | :star | :globstar | :globstar_slash
  defp translate("\\" <> <<c::utf8, rest::binary>>, acc),
    do: translate(rest, [{:lit, <<c::utf8>>} | acc])

  # `**/` — zero or more whole directories.
  defp translate("**/" <> rest, acc), do: translate(rest, [:globstar_slash | acc])
  # `**` anywhere else (`docs/**`, `**.js`, bare `**`) — anything at all.
  defp translate("**" <> rest, acc), do: translate(rest, [:globstar | acc])
  defp translate("*" <> rest, acc), do: translate(rest, [:star | acc])

  defp translate(<<q, rest::binary>>, [{kind, _} = atom | acc])
       when q in [??, ?+] and kind in [:lit, :class],
       do: translate(rest, [{:quant, atom, <<q>>} | acc])

  defp translate("[" <> rest, acc) do
    case class(rest, "") do
      {:ok, body, rest} -> translate(rest, [{:class, body} | acc])
      # Not a class the cheat sheet allows: the `[` was just a character.
      :error -> translate(rest, [{:lit, "["} | acc])
    end
  end

  defp translate(<<c::utf8, rest::binary>>, acc), do: translate(rest, [{:lit, <<c::utf8>>} | acc])
  defp translate("", acc), do: Enum.reverse(acc)

  defp render(atoms), do: Enum.map_join(atoms, &atom/1)

  defp atom({:lit, char}), do: Regex.escape(char)
  defp atom({:class, body}), do: "[" <> body <> "]"
  # The regex is byte-wise, so a quantified multibyte character is grouped.
  defp atom({:quant, {:lit, char}, q}) when byte_size(char) > 1,
    do: "(?:" <> Regex.escape(char) <> ")" <> q

  defp atom({:quant, atom, q}), do: atom(atom) <> q
  defp atom(:star), do: "[^/]*"
  defp atom(:globstar), do: ".*"
  defp atom(:globstar_slash), do: "(?:.*/)?"

  # The inside of `[...]`: alphanumerics, and ranges whose ends are both
  # lowercase letters, both uppercase, or both digits. Anything else — and
  # an empty `[]` — isn't a class.
  defp class("]" <> rest, body) when body != "", do: {:ok, body, rest}

  defp class(<<lo, ?-, hi, rest::binary>>, body) when hi != ?] do
    if range?(lo, hi), do: class(rest, body <> <<lo, ?-, hi>>), else: :error
  end

  defp class(<<c, rest::binary>>, body) when c in ?a..?z or c in ?A..?Z or c in ?0..?9,
    do: class(rest, body <> <<c>>)

  defp class(_other, _body), do: :error

  defp range?(lo, hi) do
    lo <= hi and Enum.any?([?a..?z, ?A..?Z, ?0..?9], &(lo in &1 and hi in &1))
  end
end