<commit_before>require "nokogiri"

module Markdiff
  class Differ
    # Apply given patch to given node
    # @param [Array<Hash>] patch
    # @param [Nokogiri::XML::Node] node
    def apply(patch, node)
      patch.each do |operation|
        case operation[:type]
        when :add_previous_sibling
          operation[:right_node].add_previous_sibling("<ins>#{operation[:node]}</ins>")
        when :prepend_child
          operation[:parent_node].add_child("<ins>#{operation[:node]}</ins>")
        when :remove
          operation[:node].replace("<del>#{operation[:node]}</del>")
        else
          raise "Unknown operation type: #{operation[:type].inspect}"
        end
      end
      node
    end

    # Takes parent nodes and returns a patch as an Array of operations
    # @param [Nokogiri::XML::Node] before_node
    # @param [Nokogiri::XML::Node] after_node
    # @return [Array<Hash>] Patch
    def diff(before_node, after_node)
      if before_node.to_html == after_node.to_html
        []
      else
        diff_children(before_node, after_node)
      end
    end

    private

    # Takes 2 parent nodes and recursively compare their children.
    #
    # @note There are 3 types of patch operations:
    #
    # - add_previous_sibling
    # - prepend_child
    # - remove
    #
    # @param [Nokogiri::XML::Node] before_node
    # @param [Nokogiri::XML::Node] after_node
    # @return [Array<Hash>] Patch
    def diff_children(before_node, after_node)
      patch = []
      identity_map = {}
      inverted_identity_map = {}
      before_node.children.each do |before_child|
        after_node.children.each do |after_child|
          if inverted_identity_map[after_child]
            next
          end
          if before_child.to_html == after_child.to_html
            identity_map[before_child] = after_child
            inverted_identity_map[after_child] = before_child
          end
        end
      end

      before_node.children.each do |before_child|
        if identity_map[before_child]
          next
        end
        after_node.children.each do |after_child|
          if inverted_identity_map[after_child]
            next
          end
          if before_child.name == after_child.name && !before_child.text?
            identity_map[before_child] = after_child
            inverted_identity_map[after_child] = before_child
            patch += diff(before_child, after_child)
          end
        end
      end

      before_node.children.each do |before_child|
        unless identity_map[before_child]
          patch << { node: before_child, type: :remove }
        end
      end

      after_node.children.each do |after_child|
        unless inverted_identity_map[after_child]
          right_node = after_child.next_sibling
          loop do
            case
            when inverted_identity_map[right_node]
              patch << { right_node: inverted_identity_map[right_node], node: after_child, type: :add_previous_sibling }
              break
            when right_node.nil?
              patch << { parent_node: before_node, node: after_child, type: :prepend_child }
              break
            else
              right_node = right_node.next_sibling
            end
          end
        end
      end

      patch
    end
  end
end<commit_msg>Improve type name<commit_after>require "nokogiri"

module Markdiff
  class Differ
    # Apply given patch to given node
    # @param [Array<Hash>] patch
    # @param [Nokogiri::XML::Node] node
    def apply(patch, node)
      patch.each do |operation|
        case operation[:type]
        when :add_previous_sibling
          operation[:right_node].add_previous_sibling("<ins>#{operation[:node]}</ins>")
        when :add_child
          operation[:parent_node].add_child("<ins>#{operation[:node]}</ins>")
        when :remove
          operation[:node].replace("<del>#{operation[:node]}</del>")
        else
          raise "Unknown operation type: #{operation[:type].inspect}"
        end
      end
      node
    end

    # Takes parent nodes and returns a patch as an Array of operations
    # @param [Nokogiri::XML::Node] before_node
    # @param [Nokogiri::XML::Node] after_node
    # @return [Array<Hash>] Patch
    def diff(before_node, after_node)
      if before_node.to_html == after_node.to_html
        []
      else
        diff_children(before_node, after_node)
      end
    end

    private

    # Takes 2 parent nodes and recursively compare their children.
    #
    # @note There are 3 types of patch operations:
    #
    # - add_previous_sibling
    # - add_child
    # - remove
    #
    # @param [Nokogiri::XML::Node] before_node
    # @param [Nokogiri::XML::Node] after_node
    # @return [Array<Hash>] Patch
    def diff_children(before_node, after_node)
      patch = []
      identity_map = {}
      inverted_identity_map = {}
      before_node.children.each do |before_child|
        after_node.children.each do |after_child|
          if inverted_identity_map[after_child]
            next
          end
          if before_child.to_html == after_child.to_html
            identity_map[before_child] = after_child
            inverted_identity_map[after_child] = before_child
          end
        end
      end

      before_node.children.each do |before_child|
        if identity_map[before_child]
          next
        end
        after_node.children.each do |after_child|
          if inverted_identity_map[after_child]
            next
          end
          if before_child.name == after_child.name && !before_child.text?
            identity_map[before_child] = after_child
            inverted_identity_map[after_child] = before_child
            patch += diff(before_child, after_child)
          end
        end
      end

      before_node.children.each do |before_child|
        unless identity_map[before_child]
          patch << { node: before_child, type: :remove }
        end
      end

      after_node.children.each do |after_child|
        unless inverted_identity_map[after_child]
          right_node = after_child.next_sibling
          loop do
            case
            when inverted_identity_map[right_node]
              patch << { right_node: inverted_identity_map[right_node], node: after_child, type: :add_previous_sibling }
              break
            when right_node.nil?
              patch << { parent_node: before_node, node: after_child, type: :add_child }
              break
            else
              right_node = right_node.next_sibling
            end
          end
        end
      end

      patch
    end
  end
end
{'fraction_non_alphanumeric': 0.08585247883917775, 'fraction_numerical': 0.0006045949214026602, 'mean_word_length': 2.167544279559598, 'pattern_counts': {'":': 0, '<': 33, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1965174', 'n_tokens_mistral': 1936, 'n_tokens_neox': 1920, 'n_words': 429}