duplicate_code_finder

defmodule DuplicateCodeFinder do

  @moduledoc """
    Duplicate Code Finder allows you to search for similar code blocks inside your Elixir project.
  """

  # Recursively scan directory to find elixir source files
  defp get_files(dir) do
    if File.exists?(dir) do
      {:ok, walker} = DirWalker.start_link(dir)
      walker |> DirWalker.next(100_000_000) |> Enum.filter(fn item ->
        ext = item |> String.split(".") |> Enum.reverse |> hd
        (ext == "ex") or (ext == "exs")
      end)
    else
      []
    end
  end

  defp get_ast(filename) do
    try do
      Code.string_to_quoted!(File.read!(filename))
    rescue
      _ ->
        nil
    end
  end

  # Recursive AST tree search to get all it's nodes
  defp visit(node, nodes) do
    nodes = nodes ++ [node]
    ch = children(node)
    if ch do
      new_nodes = for c <- ch do
        {_, nodes} = visit(c, nodes)
        nodes
      end
      {_, nodes} = Enum.flat_map_reduce(new_nodes, [], fn item, acc -> {item, acc ++ item} end)
      {ch, nodes}
    else
      {[], nodes}
    end
  end

  # Get all informative nodes from AST tree
  defp code_blocks(file) do
    {_, nodes} = visit(get_ast(file), [])
    nodes = nodes |> Enum.uniq |> Enum.filter(fn item ->
      case item do
        {_, _, c} ->
          cond do
            c == nil ->
              false
            is_list(c) ->
              true
            true ->
              false
          end
        nil ->
          false
        _ ->
          try do
            _ = Enum.into(node, %{})
            false
          rescue
            _ -> is_tuple(item)
          end
      end
    end)
    {_, nodes} = for n <- nodes do
      if is_list(n) and length(n) > 1 do
        len = length(n)
        {_, tmp} = for i <- 0..len - 2 do
          for j <- i+1..len - 1 do
            Enum.slice(n, i..j)
          end
        end
        tmp = tmp |> Enum.flat_map_reduce([], fn item, acc -> {item, item ++ acc} end)
        tmp
      else
        [n]
      end
    end |> Enum.flat_map_reduce([], fn item, acc -> {item, item ++ acc} end)
    # keep filename connected to the nodes
    for n <- nodes do
      {file, n}
    end
  end

  defp read_content(map, files) do
    if length(files) > 0 do
      file = hd(files)
      map = map |> Map.put(file, File.read!(file) |> String.split("\n"))
      read_content(map, tl(files))
    else
      map
    end
  end

  defp get_configs() do
    {d_dirs, d_min_depth, d_min_length} = {["lib", "config", "web"], 1, 3}
    dirs = Application.get_env(:duplicate_code_finder, :dirs)
    min_depth = Application.get_env(:duplicate_code_finder, :min_depth)
    min_length = Application.get_env(:duplicate_code_finder, :min_length)
    f = fn i, j ->
      if i do
        i
      else
        j
      end
    end
    dirs = f.(dirs, d_dirs)
    min_depth = f.(min_depth, d_min_depth)
    min_length = f.(min_length, d_min_length)
    {dirs, min_depth, min_length}
  end

  # Main function to find equal code parts.
  # dirs - directories to scan for elixir source files
  # export_file - if not nil, write results to the file by this path
  def show_similar(dirs \\ nil, export_file \\ nil) do
    {directories, min_depth, min_length} = get_configs()
    dirs = if dirs do
      dirs
    else
      directories
    end
    # scan dirs
    files = for d <- dirs do
      get_files(d)
    end
    {_, files} = files |> Enum.flat_map_reduce([], fn item, acc -> {item, acc ++ item} end)
    IO.puts ""
    IO.puts "Reading files..."
    nodes = for file <- files do
      IO.puts file
      code_blocks(file)
    end
    IO.puts ""
    IO.puts "Searching for similarities..."
    {_, nodes} = Enum.flat_map_reduce(nodes, [], fn item, acc -> {item, acc ++ item} end)
    # get map of file contents (key, balue = filename, content)
    content = read_content(Map.new(), files)
    # get grouped equal code blocks
    groups = equal_code(nodes, min_depth, min_length)
    space = ["---------------------------------------------------------------"]
    # get data to show
    all_data = for group <- groups do
      gr = for item <- group |> Enum.reverse do
        {file, {min, max}} = item
        min = min - 1
        max = max - 1
        c = Enum.slice(content[file], min..max)

        # TODO: last line indents (end of blocks are not in output)
        # f = fn i, acc ->
        #   if i == " " |> to_charlist |> hd do
        #     {:cont, acc + 1}
        #   else
        #     # IO.inspect i
        #     {:halt, acc}
        #   end
        # end
        # first = c |> hd |> to_charlist |> Enum.reduce_while(0, f)
        # last = c |> Enum.reverse |> hd |> to_charlist |> Enum.reduce_while(0, f)
        # # IO.inspect {first, last}
        # {c, min, max} = if first != last do
        #   item = Enum.slice(content[file], max+1..max+1)
        #   {c ++ item, min, max+1}
        # else
        #   {c, min, max}
        # end

        c = Enum.zip(min + 1..max + 1, c)
        c = for l <- c do
          {number, line} = l
          "#{number}: #{line}"
        end
        ["#{file}:"] ++ c ++ [""]
      end
      {_, gr} = Enum.flat_map_reduce(gr, [], fn item, acc -> {item, acc ++ item} end)
      gr ++ space
    end
    {_, all_data} = Enum.flat_map_reduce(all_data, [], fn item, acc -> {item, acc ++ item} end)
    nothing_found = "There are no duplicates"
    if export_file == nil do
      for item <- all_data do
        IO.puts item
      end
      if length(all_data) == 0 do
        IO.puts nothing_found
      end
    else
      all_data = if length(all_data) == 0 do
        [nothing_found]
      else
        all_data
      end
      write_file(export_file, all_data)
    end
    nil
  end

  defp write_file(filename, data) do
    try do
      {:ok, file} = File.open(filename, [:write])
      for d <- data do
        IO.binwrite(file, "#{d}\n")
      end
      File.close(file)
    rescue
      _ ->
        :error
    end
  end

  # Transform data from pairs to groups by equality
  defp group_equals(equals, grouped) do
    len = length(equals)
    if len > 0 do
      # fetch the first equal part from equals list
      {{n1, n2}, {lines1, lines2}, {s1, _}} = equals |> Enum.fetch!(0)
      # find pairs which have the same shape as the first pair
      group = if len > 1 do
        for i <- 1..len - 1 do
          {{n3, n4}, {lines3, lines4}, {_, s2}} = equals |> Enum.fetch!(i)
          if is_equal(s1, s2) do
            [{n3, lines3}, {n4, lines4}]
          else
            []
          end
        end
      else
        [[]]
      end
      {_, group} = Enum.flat_map_reduce(group, [], fn item, acc -> {item, acc ++ item} end)
      group = [{n1, lines1}, {n2, lines2}] ++ group
      group = group |> Enum.filter(fn item -> item != nil end) |> Enum.uniq
      # add new group
      grouped = grouped ++ [group]
      # filter from equals list all pairs we found
      equals = Enum.filter(equals, fn item ->
        {{n1, n2}, {lines1, lines2}, _} = item
        not ({n1, lines1} in group and {n2, lines2} in group)
      end)
      # run recursively with new {equals, grouped}
      group_equals(equals, grouped)
    else
      {[], grouped}
    end
  end

  # Find equal code parts
  defp equal_code(nodes, min_depth, min_length) do
    # calculate shapes only once
    nodes = for {file, n} <- nodes do
      {{n, file}, get_shape(n)}
    end
    # filter short blocks, non deep blocks
    nodes = Enum.filter(nodes, fn {_, %{lines: {min, max}, depth: depth}} ->
      (max != nil) and (min != nil) and (depth >= min_depth) and (max - min + 1 >= min_length)
      # (max != nil) and (min != nil) and (max - min >= min_length)
    end)
    nodes = nodes |> Enum.reverse |> Enum.uniq_by(fn {_, s} -> s[:lines] end) |> Enum.reverse

    len = length(nodes)
    # compare blocks with each other
    # if blocks are not equal, they are compared very fast
    # (do not go deep with recursion)
    equals = if len > 2 do
      for i <- 0..(len - 2) do
        for j <- i+1..(len - 1) do
          {{n1, file1}, s1} = Enum.fetch!(nodes, i)
          {{n2, file2}, s2} = Enum.fetch!(nodes, j)
          if is_equal(s1, s2) do
            {{{n1, file1}, {n2, file2}}, {s1[:lines], s2[:lines]}, {s1, s2}}
          end
        end
      end
    else
      [[]]
    end
    {_, equals} = Enum.flat_map_reduce(equals, [], fn item, acc -> {item, acc ++ item} end)
    equals = Enum.filter(equals, fn item -> item != nil end)
    # filter subsamples
    equals = for e1 <- equals do
      arr = for e2 <- equals do
        {{_, _}, {{min1, max1}, {min2, max2}}, {s1, _}} = e1
        {{_, _}, {{min3, max3}, {min4, max4}}, {s3, _}} = e2
        (s1[:depth] < s3[:depth]) and
        (min1 >= min3) and
        (max1 <= max3) and
        (min2 >= min4) and
        (max2 <= max4)
      end
      {e1, arr}
    end
    equals = for {e, is_subsample} <- equals do
      if Enum.any?(is_subsample) do
        nil
      else
        e
      end
    end
    equals = equals |> Enum.filter(fn item -> item != nil end)
    # transform data from pairs to groups by equality
    {_, grouped} = group_equals(equals, [])
    # keep only filename, {min, max} line numbers of block
    for group <- grouped do
      for item <- group do
        {{_, file}, lines} = item
        {file, lines}
      end
    end
  end

  # Get children of the node
  defp children(node) do
    case node do
      {_, _, nodes} ->
        nodes
      _ ->
        try do
          # works when node like [do: data1, else: data2]
          # returns [data1, data2]
          node = Enum.into(node, %{})
          Map.values(node)
        rescue
          _ ->
            if is_list(node) do
              node
            else
              nil
            end
        end
    end
  end

  # Comparison of 2 nodes by their shapes
  defp is_equal(s1, s2) do
    # assume different var names as equal
    current_eq = (s1[:variable] and s2[:variable]) or (s1[:name] == s2[:name])
    # assume different var names as different
    # current_eq = s1[:name] == s2[:name]
    eq = if current_eq do
      if s1[:depth] == s2[:depth] and length(s1[:children]) == length(s2[:children]) do
        ch_eq = for {c1, c2} <- Enum.zip(s1[:children], s2[:children]) do
          is_equal(c1, c2)
        end
        Enum.all?(ch_eq)
      end
    end
    if eq == nil do
      false
    else
      eq
    end
  end

  # Get structured shape of the node for comparison
  defp get_shape(node) do
    ch = children(node)
    ch = if ch do
      for c <- ch do
        get_shape(c)
      end
    else
      []
    end
    depth = if length(ch) == 0 do
      1
    else
      Enum.max_by(ch, fn item -> item[:depth] end)[:depth] + 1
    end
    case node do
      {name, _, content} ->
        # is node a variable?
        var = if content == nil do
          true
        else
          false
        end
        name = if is_atom(name) do
          name
        else
          "_"
        end
        %{name: name, lines: get_lines(node), children: ch, variable: var, depth: depth}
      _ ->
        if is_integer(node) or is_float(node) do
            %{name: node, lines: get_lines(node), children: ch, variable: false, depth: depth}
        else
            %{name: "_", lines: get_lines(node), children: ch, variable: false, depth: depth}
        end
    end
  end

  # Recursively go through the node and finds {min, max} line numbers
  defp get_lines(node, main \\ true) do
    current = case node do
      {_, data, _} ->
        case data do
          [line: l] ->
            l
          [counter: _, line: l] ->
            l
          _ ->
            nil
        end
      _ ->
        nil
    end
    ch = children(node)
    from_ch = if ch do
      for c <- ch do
        get_lines(c, false)
      end
    else
      []
    end
    {_, from_ch} = Enum.flat_map_reduce(from_ch, [], fn item, acc -> {item, acc ++ item} end)
    current = Enum.filter(from_ch, fn item -> item != nil end) ++ [current]
    current = Enum.uniq(current)
    if main do
      {Enum.min(current), Enum.max(current)}
    else
      current
    end
  end

end