Sort items "naturally" in menu, summary, function list, etc.

[eksperimental]

Functions in the menu are current listed like this:

• reraise/2
• reraise/3
• send/2
• sigil_C/2
• sigil_D/2
• sigil_N/2
• sigil_R/2
• sigil_S/2
• sigil_T/2
• sigil_U/2
• sigil_W/2
• sigil_c/2
• sigil_r/2
• sigil_s/2
• sigil_w/2
• spawn/1
• spawn/3

I was trying to hop from the documentation from sigil_S to sigil_s, and i found it counter intuitive that they were that far apart, specially inside the module. I think we should make it more "natural".

[josevalim]

Sounds good to me. A PR is welcome.

[eksperimental]

Sounds good to me. A PR is welcome.

If anybody wants to tackle it, please be welcome. If not, I will eventually take care of it. As of now, I am kind of busy with other stuff.

[eksperimental]

Do we want a quick and dirty solution, or is it OK to add an existing library to sort solve this?

[josevalim]

We should avoid libraries in ExDoc because otherwise your documentation generation tool can impose restrictions on your actual lib/app code. :)

[eksperimental]

We should avoid libraries in ExDoc because otherwise your documentation generation tool can impose restrictions on your actual lib/app code. :)

A library like this is likely to to not have dependencies... given this and the Elixir requirements match the ones of ExDoc, would this still be an issue?

[josevalim]

First, that library will be unable to use ExDoc to publish their own docs, so we would need to coordinate at least that with them.

Second, any user of that library may not be limited by ExDoc particular requirements. So my answer would still be a no. :)

[eksperimental]

Sounds good to me. A PR is welcome.

If anybody wants to tackle it, please be welcome. If not, I will eventually take care of it. As of now, I am kind of busy with other stuff.

I am already taking care of this.

[am-kantox]

Since the “natural” in “natural order” is quite specific here, I’d propose the custom sorter that is explicitly optimized for valid elixir names (unquoted Unicode atoms, variables, and calls to be in NFC form).

It is nimble for 99% of the input and has a fallback to properly sort exotics like Greek/Cyrillics and/or umlauts and other diacritics.

defmodule M do
  @case_shift ?a - ?A + 1
  @lowercase_ascii Enum.to_list(?a..?z)
  @uppercase_ascii Enum.to_list(?A..?Z)
  @ascii_letters @lowercase_ascii ++ @uppercase_ascii
  @digits Enum.to_list(?0..?9)
  @service [?_]
  @ascii @ascii_letters ++ @digits ++ @service

  defguard is_same_group(c1, c2)
           when (c1 in @lowercase_ascii and c2 in @lowercase_ascii) or
                  (c1 in @uppercase_ascii and c2 in @uppercase_ascii)

  @spec sorter(String.t(), String.t()) :: boolean()
  def sorter(<<c::8, tl1::binary>>, <<c::8, tl2::binary>>) when c in @ascii,
    do: sorter(tl1, tl2)

  def sorter(<<c::utf8, tl1::binary>>, <<c::utf8, tl2::binary>>), do: sorter(tl1, tl2)

  def sorter(<<c1::8, _::binary>>, <<c2::8, _::binary>>) when is_same_group(c1, c2),
    do: c1 <= c2

  def sorter(<<c1::8, _::binary>>, <<c2::8, _::binary>>)
      when c1 in @lowercase_ascii and c2 in @uppercase_ascii,
      do: c1 <= c2 + @case_shift

  def sorter(<<c1::8, _::binary>>, <<c2::8, _::binary>>)
      when c1 in @uppercase_ascii and c2 in @lowercase_ascii,
      do: c1 + @case_shift <= c2

  def sorter(<<c1::8, _::binary>>, <<c2::8, _::binary>>) when c1 in @ascii and c2 in @ascii,
    do: c1 <= c2

  def sorter(s1, s2) do
    [s1, s2]
    |> Enum.map(&String.normalize(&1, :nfd))
    |> Enum.map(&String.split(&1, "", trim: true, parts: 2))
    |> case do
      [[c, ""], [c, <<d::utf8, _::binary>>]] ->
        not (c in @digits and d in @digits)

      [[c, <<d::utf8, _::binary>>], [c, ""]] ->
        c in @digits and d in @digits

      [[c, tl1], [c, tl2]] ->
        sorter(tl1, tl2)

      [[c1 | _], [c2 | _]] ->
        cond do
          String.upcase(c1) == c2 -> true
          c1 == String.upcase(c2) -> false
          true -> String.upcase(c1) <= String.upcase(c2)
        end
    end
  end

  #############################################################################

  @input ~w|
    reraise/2
    reraise/3
    send/2
    sigil_C/2
    sigil_D/2
    sigil_c/2
    λ/1
    spawn/1
    spawn/3
    Λ/1
    a1/1
    a0/1
    a10/1
    a1_0/1
    a_0/1
    äpfeln/1
    Äpfeln/1
    умножить/1
    Вычесть/1
    вычесть/1
  |

  @sorted ~w|
    a0/1
    a1/1
    a10/1
    a1_0/1
    a_0/1
    äpfeln/1
    Äpfeln/1
    reraise/2
    reraise/3
    send/2
    sigil_c/2
    sigil_C/2
    sigil_D/2
    spawn/1
    spawn/3
    λ/1
    Λ/1
    вычесть/1
    Вычесть/1
    умножить/1
  |

  def test(), do: Enum.sort(@input, &sorter/2) == @sorted
end

[josevalim]

@am-kantox that's an interesting approach, thanks for sharing! I wonder if we can simplify it by doing to_charlist and then sorting everything as usual for the ascii ones?

The reason why I think we can simplify this further is because mixed case is extremely uncommon, so I think we don't really need to worry about it besides ascii.

[am-kantox]

mixed case is extremely uncommon

That’s right, but it’s still handled in the last clause, that’s why I said in 99% of cases we go through bitstream pattern match. I am not sure if charlist match would be faster, are you? I could have done benchmarks tonight.

we don't really need to worry about it besides ascii

Since it’s the last clause, I don’t get why would not we handle it as well. ASCII goes through the first clauses.

Several clauses are still needed because of ordering here:

  a0/1
  a1/1
  a10/1
  a1_0/1

[josevalim]

Here is the alternative take I propose:

defmodule Sorter do
  def to_sorted_charlist(string) do
    string
    |> :unicode.characters_to_nfkd_list()
    |> Enum.map(fn
      char when char in ?a..?z -> char - 31.5
      char -> char
    end)
  end
end

ExUnit.start()

defmodule Example do
  use ExUnit.Case, async: true

  @input ~w|
    reraise/2
    reraise/3
    send/2
    sigil_C/2
    sigil_D/2
    sigil_c/2
    λ/1
    spawn/1
    spawn/3
    Λ/1
    a1/1
    a0/1
    a10/1
    a1_0/1
    a_0/1
    äpfeln/1
    Äpfeln/1
    умножить/1
    Вычесть/1
    вычесть/1
  |

  @sorted ~w|
    Äpfeln/1
    a0/1
    a1/1
    a10/1
    a1_0/1
    a_0/1
    äpfeln/1
    reraise/2
    reraise/3
    send/2
    sigil_C/2
    sigil_c/2
    sigil_D/2
    spawn/1
    spawn/3
    Λ/1
    λ/1
    Вычесть/1
    вычесть/1
    умножить/1
  |

  test "sort" do
    assert Enum.sort_by(@input, &Sorter.to_sorted_charlist/1) == @sorted
  end
end

It does list uppercase first and then lowercase, but that's the order recommended by Unicode. You can also change the offset to -32.5 to get lowercase first. Function names cannot start in lowercase though, so it only comes up on disambiguation.

[am-kantox]

The only glitch I see is Äpfeln/1 and äpfeln/1 are not consequent. I’d appreciate seeing them together, but AFAICT that’s impossible without extra clauses to handle diacritics.

Also, I’ve just figured out that clauses for ASCII might be actually generated (as those in String.{down,up}case/1) to avoid going through :unicode.characters_to_nfkd_list() for long strings.

OTOH, the number of items to sort in this case barely exceeds several dozens, so I surely like your proposal more.

[josevalim]

The only glitch I see is Äpfeln/1 and äpfeln/1 are not consequent.

Right, as I said above, it won't happen in practice because identifiers can't start with uppercase. Also note this is order defined by Unicode too (Á comes before a).

OTOH, the number of items to sort in this case barely exceeds several dozens, so I surely like your proposal more.

I also use sort_by, which is not pairwise, so it should be faster generally.

[am-kantox]

it won't happen in practice because identifiers can't start with uppercase

Well, technically it will.

die_äpfeln/1
die_Äpfeln/1

but we should not care much about it, yes.