Remove quadratic complexity from internal APIs · elixir-lang/elixir@37a6b02 · GitHub
Skip to content

Commit 37a6b02

Browse files
committed
Remove quadratic complexity from internal APIs
1 parent 7fd7a77 commit 37a6b02

4 files changed

Lines changed: 84 additions & 55 deletions

File tree

‎lib/elixir/lib/code/fragment.ex‎

Lines changed: 29 additions & 29 deletions

‎lib/elixir/lib/code/normalizer.ex‎

Lines changed: 37 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -202,7 +202,7 @@ defmodule Code.Normalizer do
202202

203203
if args != [] and match?([_ | _], last_arg) and keyword?(last_arg) do
204204
args = normalize_args(args, state)
205-
kw_list = normalize_kw_args(last_arg, state, true)
205+
kw_list = normalize_kw_args(last_arg, state, 0)
206206
{:{}, meta, args ++ kw_list}
207207
else
208208
normalize_call(quoted, state)
@@ -214,7 +214,7 @@ defmodule Code.Normalizer do
214214
value =
215215
cond do
216216
keyword?(value) and value != [] ->
217-
normalize_kw_args(value, state, true)
217+
normalize_kw_args(value, state, 0)
218218

219219
is_list(value) ->
220220
normalize_literal(value, meta, state)
@@ -286,7 +286,7 @@ defmodule Code.Normalizer do
286286
state = %{state | parent_meta: meta}
287287

288288
if match?([_ | _], right) and keyword?(right) do
289-
{:__block__, meta, [{do_normalize(left, state), normalize_kw_args(right, state, true)}]}
289+
{:__block__, meta, [{do_normalize(left, state), normalize_kw_args(right, state, 0)}]}
290290
else
291291
{:__block__, meta, [{do_normalize(left, state), do_normalize(right, state)}]}
292292
end
@@ -317,7 +317,7 @@ defmodule Code.Normalizer do
317317
meta
318318
end
319319

320-
{:__block__, meta, [normalize_kw_args(list, state, false)]}
320+
{:__block__, meta, [normalize_kw_args(list, state, keyword_start(list))]}
321321
end
322322
end
323323

@@ -479,7 +479,7 @@ defmodule Code.Normalizer do
479479
end
480480

481481
defp normalize_map_args(args, state) do
482-
Enum.map(normalize_kw_args(args, state, false), fn
482+
Enum.map(normalize_kw_args(args, state, keyword_start(args)), fn
483483
{:__block__, _, [{_, _} = pair]} -> pair
484484
pair -> pair
485485
end)
@@ -512,15 +512,17 @@ defmodule Code.Normalizer do
512512
{form, meta, leading_args ++ [kw_blocks]}
513513
end
514514

515-
defp normalize_kw_args(elems, state, keyword?)
515+
# The last argument is how many elements are left until the
516+
# trailing keyword list starts (0 if we are already in it)
517+
defp normalize_kw_args(elems, state, until_keyword)
516518

517519
defp normalize_kw_args(
518-
[{{:__block__, key_meta, [key]}, value} = first | rest] = current,
520+
[{{:__block__, key_meta, [key]}, value} = first | rest],
519521
state,
520-
keyword?
522+
until_keyword
521523
)
522524
when is_atom(key) do
523-
keyword? = keyword? or keyword?(current)
525+
keyword? = until_keyword == 0
524526

525527
first =
526528
if key_meta[:format] == :keyword and not keyword? do
@@ -531,11 +533,11 @@ defmodule Code.Normalizer do
531533
first
532534
end
533535

534-
[first | normalize_kw_args(rest, state, keyword?)]
536+
[first | normalize_kw_args(rest, state, max(until_keyword - 1, 0))]
535537
end
536538

537-
defp normalize_kw_args([{left, right} | rest] = current, state, keyword?) do
538-
keyword? = keyword? or keyword?(current)
539+
defp normalize_kw_args([{left, right} | rest], state, until_keyword) do
540+
keyword? = until_keyword == 0
539541

540542
left =
541543
if keyword? do
@@ -555,17 +557,27 @@ defmodule Code.Normalizer do
555557
_ -> {:__block__, meta_line(state), [{left, right}]}
556558
end
557559

558-
[pair | normalize_kw_args(rest, state, keyword?)]
560+
[pair | normalize_kw_args(rest, state, max(until_keyword - 1, 0))]
559561
end
560562

561-
defp normalize_kw_args([first | rest], state, keyword?) do
562-
[do_normalize(first, state) | normalize_kw_args(rest, state, keyword?)]
563+
defp normalize_kw_args([first | rest], state, until_keyword) do
564+
[do_normalize(first, state) | normalize_kw_args(rest, state, max(until_keyword - 1, 0))]
563565
end
564566

565-
defp normalize_kw_args([], _state, _keyword?) do
567+
defp normalize_kw_args([], _state, _until_keyword) do
566568
[]
567569
end
568570

571+
defp keyword_start(list) do
572+
length(list) - keyword_suffix_length(:lists.reverse(list), 0)
573+
end
574+
575+
defp keyword_suffix_length([head | tail], acc) do
576+
if keyword_pair?(head), do: keyword_suffix_length(tail, acc + 1), else: acc
577+
end
578+
579+
defp keyword_suffix_length([], acc), do: acc
580+
569581
defp normalize_args(args, state) do
570582
Enum.map(args, &do_normalize(&1, state))
571583
end
@@ -619,21 +631,20 @@ defmodule Code.Normalizer do
619631
end
620632
end
621633

622-
defp keyword?([{{:__block__, key_meta, [key]}, _} | rest]) when is_atom(key) do
623-
if key_meta[:format] == :keyword do
624-
keyword?(rest)
625-
else
626-
false
627-
end
634+
defp keyword?([head | rest]), do: keyword_pair?(head) and keyword?(rest)
635+
defp keyword?([]), do: true
636+
defp keyword?(_other), do: false
637+
638+
defp keyword_pair?({{:__block__, key_meta, [key]}, _}) when is_atom(key) do
639+
key_meta[:format] == :keyword
628640
end
629641

630-
defp keyword?([{key, _value} | rest]) when is_atom(key) do
642+
defp keyword_pair?({key, _value}) when is_atom(key) do
631643
case Atom.to_charlist(key) do
632644
~c"Elixir." ++ _ -> false
633-
_ -> keyword?(rest)
645+
_ -> true
634646
end
635647
end
636648

637-
defp keyword?([]), do: true
638-
defp keyword?(_other), do: false
649+
defp keyword_pair?(_other), do: false
639650
end

‎lib/elixir/test/elixir/code_fragment_test.exs‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -245,6 +245,14 @@ defmodule CodeFragmentTest do
245245
{:alias, {:local_or_var, ~c"__MODULE__"}, ~c"Wor"}
246246

247247
assert CF.cursor_context("@foo.Wor") == {:alias, {:module_attribute, ~c"foo"}, ~c"Wor"}
248+
249+
assert CF.cursor_context("Hello.Big.Wor") == {:alias, ~c"Hello.Big.Wor"}
250+
251+
assert CF.cursor_context("hello.Big.World") ==
252+
{:alias, {:local_or_var, ~c"hello"}, ~c"Big.World"}
253+
254+
assert CF.cursor_context("@foo.Big.Wor") ==
255+
{:alias, {:module_attribute, ~c"foo"}, ~c"Big.Wor"}
248256
end
249257

250258
test "structs" do
@@ -279,6 +287,14 @@ defmodule CodeFragmentTest do
279287

280288
assert CF.cursor_context("%@foo.Wor") ==
281289
{:struct, {:alias, {:module_attribute, ~c"foo"}, ~c"Wor"}}
290+
291+
assert CF.cursor_context("%Hello.Big.Wor") == {:struct, ~c"Hello.Big.Wor"}
292+
293+
assert CF.cursor_context("%__MODULE__.Big.Wor") ==
294+
{:struct, {:alias, {:local_or_var, ~c"__MODULE__"}, ~c"Big.Wor"}}
295+
296+
assert CF.cursor_context("%@foo.Big.Wor") ==
297+
{:struct, {:alias, {:module_attribute, ~c"foo"}, ~c"Big.Wor"}}
282298
end
283299

284300
test "unquoted atom" do

‎lib/elixir/test/elixir/code_normalizer/quoted_ast_test.exs‎

Lines changed: 2 additions & 0 deletions

0 commit comments

Comments
 (0)