Реализация зиппера для ruby

zipper.rb

require_relative "./node"

module AST
  ##
  # Реализация зиппера для обхода структуры AST.
  #
  # Что такое зиппер? Это паттерн из функционального программирования, предлагаемый
  # в качестве более продвинутой замены визиторов. По сути энумератор (или курсор),
  # умеет ходить не только вперёд/назад, но и вверх/вниз по дереву. Кроме этого
  # во время обхода дерева зиппер позволяет нам удалять/заменять/добавлять ноды
  # на лету и при этом продолжить проход по ним. Это особенно полезно, т.к.
  # структура данных дерева иммутабельна и там где с визиторами нам понадобиться
  # n проходов, зиппер справится за один. Также зиппер удобно использовать для
  # реализаций классических обходов по графу (bread-first, depth-first, ...).
  #
  # Идея и реализация была частично позаимствована из https://github.com/frankshearar/zipr
  # Объект является иммутабельным — все методы которые меняют фокус или что-то изменяют
  # возвращают новую копию зиппера.
  #
  # Ссылки для ознакомления с паттерном:
  #   - http://www.ibm.com/developerworks/library/j-treevisit
  #   - http://learnyouahaskell.com/zippers
  #   - http://www.haskell.org/haskellwiki/Zipper
  #
  # ВНИМАНИЕ! На деревья смотреть в моноширинном шрифте!
  #
  # @example
  #
  #   tree =
  #    s( :root,
  #      s( :branch_1,
  #        s( :leaf, 1, 2 ))
  #      s( :branch_2,
  #        s( :leaf, 3, 4 )))
  #
  #   Zipper.new( tree ).down.right.down.down.right.replace( 31337 ).insert_right( 42 ).root.value #=>
  #    s( :root,
  #      s( :branch_1,
  #        s( :leaf, 1, 2 ))
  #      s( :branch_2,
  #        s( :leaf, 3, 31337, 42 )))
  #
  class Zipper
    # Класс ошибки навигации по дереву
    class NavigationError < Exception; end

    # Класс ошибки модификации дерева
    class ModificationError < Exception; end

    # Значение в фокусе зиппера
    # @return [AST::Node, Object]
    attr_reader :value

    # Текущий контекст
    # @see AST::Zipper::Context
    # @return [AST::Zipper::Context]
    attr_reader :context

    ##
    # Создаёт новый экземпляр зиппера (объект заморожен!).
    #
    # @param [AST::Node, Object] текущий элемент дерева
    # @param [AST::Zipper::Context] контекст (служебный параметр, не менять!)
    #
    def initialize( value, context = Context.new )
      @value = value
      @context = context
      self.freeze
    end

    ##
    # Является ли элемент в фокусе корневым?
    # Корневой элемент – это элемент с которого мы начали обход.
    # Мы не можем двигаться из корневого элемента никуда кроме как вниз.
    #
    # @return [true, false]
    #
    def root?
      context.root?
    end

    ##
    # Является ли элемент в фокусе самым левым на данном уровне иерархии?
    #
    #    ○
    #   ╱ ╲
    #  ○   ○
    #  ↑
    #
    # @return [true, false]
    #
    def leftmost?
      context.left_nodes.empty?
    end

    ##
    # Является ли элемент в фокусе самым левым на данном уровне иерархии?
    #
    #    ○
    #   ╱ ╲
    #  ○   ○
    #      ↑
    #
    # @return [true, false]
    #
    def rightmost?
      context.right_nodes.empty?
    end

    ##
    # Является ли элемент в фокусе терминальным?
    # Терминальными являются ноды без дочерних элементов и литералы.
    # Мы не можем двигаться вниз из терминалов.
    #
    #      ○
    #     ╱ ╲
    #    ○  42
    #   ╱    ↑
    #  ○
    #  ↑
    #
    # @return [true, false]
    #
    def terminal?
      literal? || value.children.empty?
    end

    ##
    # Является ли элемент в фокусе литералом?
    # Литералом считается всё кроме экземпляров AST::Node.
    #
    # @return [true, false]
    #
    def literal?
      not value.is_a? AST::Node
    end

    ##
    # Переводит фокус на корневой элемент.
    # Чаще всего используется, чтобы вернуть результирующее дерево по окончании
    # обхода и модификации (eg. root.value).
    #
    #      ○           ○ ←
    #     ╱ ╲         ╱ ╲
    #    ○   ○  ⇀    ○   ○
    #   ╱ ╲         ╱ ╲
    #  ○   ○       ○   ○
    #  ↑
    #
    # @return [AST::Zipper]
    #
    def root
      # Идем вверх до конца
      if root?
        self
      else
        up.root
      end
    end

    ##
    # Переводит фокус вниз на самый левый потомок ноды в текущем фокусе.
    #
    #      ○ ←         ○
    #     ╱ ╲         ╱ ╲
    #    ○   ○  ⇀  → ○   ○
    #   ╱ ╲         ╱ ╲
    #  ○   ○       ○   ○
    #
    # @return [AST::Zipper]
    #
    def down
      # Мы не можем идти вниз из терминалов
      if not terminal?
        Zipper.new( value.children.first, Context.new(
          path: context,
          parent_node: value,
          left_nodes: [],
          right_nodes: value.children.drop( 1 ),
          is_changed: context.is_changed
        ))
      else
        raise NavigationError, "Can't navigate down from terminal node."
      end
    end

    ##
    # Переводит фокус вверх на родительский элемент элемента в текущем фокусе.
    #
    #      ○           ○ ←
    #     ╱ ╲         ╱ ╲
    #  → ○   ○  ⇀    ○   ○
    #   ╱ ╲         ╱ ╲
    #  ○   ○       ○   ○
    #
    # @return [AST::Zipper]
    #
    def up
      # Выше корня идти некуда
      if not context.root?

        # В этом месте и происходит вся магия по модификации дерева:
        # мы смотрим флаг изменения в контесте и если он выставлен, то вместо
        # ноды исходного дерева возвращаем изменённую ноду c новыми потомками.

        if context.is_changed
          Zipper.new \
            context.parent_node.alter( children: context.left_nodes + [ value ] + context.right_nodes ),
            context.path.alter( is_changed: true )
        else
          Zipper.new \
            context.parent_node,
            context.path
        end
      else
        raise NavigationError, "Can't navigate up from root node."
      end
    end

    ##
    # Переводит фокус на элемент левее текущего элемента в фокусе.
    #
    #      ○           ○
    #     ╱ ╲         ╱ ╲
    #    ○   ○  ⇀    ○   ○
    #   ╱ ╲         ╱ ╲
    #  ○   ○       ○   ○
    #      ↑       ↑
    #
    # @return [AST::Zipper]
    #
    def left
      # Мы можем двигаться влево если там ещё остались элементы
      if context.left_nodes.any?
        Zipper.new( context.left_nodes.last, context.alter(
          left_nodes: context.left_nodes[ 0 .. -2 ],
          right_nodes: [ value ] + context.right_nodes
        ))
      else
        raise NavigationError, "Can't navigate left from leftmost node."
      end
    end

    ##
    # Переводит фокус на самый левый элемент на текущем уровне иерархии.
    #
    #     ○           ○
    #   ╱ | ╲   ⇀   ╱ | ╲
    #  ○  ○  ○     ○  ○  ○
    #        ↑     ↑
    #
    # @return [AST::Zipper]
    #
    def leftmost
      # Если мы уже скраю ничего не делаем
      if context.left_nodes.empty?
        self
      else
        all_but_leftmost = context.left_nodes.drop( 1 )

        Zipper.new( context.left_nodes.first, context.alter(
          left_nodes: [],
          right_nodes: all_but_leftmost + [ value ] + context.right_nodes
        ))
      end
    end

    ##
    # Переводит фокус на элемент правее текущего элемента в фокусе.
    #
    #      ○           ○
    #     ╱ ╲         ╱ ╲
    #    ○   ○  ⇀    ○   ○
    #   ╱ ╲         ╱ ╲
    #  ○   ○       ○   ○
    #  ↑               ↑
    #
    # @return [AST::Zipper]
    #
    def right
      # Мы можем двигаться вправо если там ещё остались элементы
      if context.right_nodes.any?
        Zipper.new( context.right_nodes.first, context.alter(
          left_nodes: context.left_nodes + [ value ],
          right_nodes: context.right_nodes.drop( 1 ),
        ))
      else
        raise NavigationError, "Can't navigate right from rightmost node."
      end
    end

    ##
    # Переводит фокус на самый правый элемент на текущем уровне иерархии.
    #
    #     ○           ○
    #   ╱ | ╲   ⇀   ╱ | ╲
    #  ○  ○  ○     ○  ○  ○
    #  ↑                 ↑
    #
    # @return [AST::Zipper]
    #
    def rightmost
      # Если мы уже скраю ничего не делаем
      if context.right_nodes.empty?
        self
      else
        all_but_rightmost = context.right_nodes[ 0 .. -2 ]

        Zipper.new( context.right_nodes.last, context.alter(
          left_nodes: context.left_nodes + [ value ] + all_but_rightmost,
          right_nodes: []
        ))
      end
    end

    ##
    # Заменяет элемент в фокусе на новый элемент.
    #
    # @param [AST::Node, Object] new_node новое значение элемента
    # @return [AST::Zipper]
    #
    def replace( new_node )
      # Ничего не делаем, если значение не меняется
      if new_node == value
        return self
      else
        return Zipper.new( new_node, context.alter( is_changed: true ))
      end
    end

    ##
    # Удаляет элемент в фокусе переводя фокус левее или выше при отсутствии элементов левее.
    #
    #      ○           ○
    #     ╱ ╲         ╱
    #    ○   ○  ⇀  → ○
    #   ╱ ╲  ↑      ╱ ╲
    #  ○   ○       ○   ○
    #
    #      ○         ○ ←
    #     ╱ ╲       ╱ ╲
    #  → ○   ○  ⇀  ○   ○
    #   ╱ ╲
    #  ○    ○
    #
    # @return [AST::Zipper]
    #
    def remove
      # Нельзя удалять корневой элемент!
      if not context.root?
        # Левее нет нод -- переходим вверх, иначе -- влево
        if context.left_nodes.empty?
          Zipper.new( context.parent_node.alter( children: context.right_nodes ), context.alter( is_changed: true ))
        else
          Zipper.new( context.left_nodes.last, context.alter(
            left_nodes: context.left_nodes.drop( 1 ),
            is_changed: true
          ))
        end
      else
        raise ModificationError, "Can't remove root node."
      end
    end

    ##
    # Не меняя фокуса добавляет новый элемент левее элемента в фокусе.
    #
    #      ○            ○
    #     ╱ ╲         ╱ | ╲
    #    ○   ○  ⇀    ○  ⊕  ○
    #   ╱ ╲  ↑      ╱ ╲    ↑
    #  ○   ○       ○   ○
    #
    # @param [AST::Node, Object] new_node новый элемент
    # @return [AST::Zipper]
    #
    def insert_left( new_node )
      # Нельзя добавить элемент левее корневого элемент
      if not context.root?
        Zipper.new( value, context.alter(
          left_nodes: context.left_nodes + [ new_node ],
          is_changed: true
        ))
      else
        raise ModificationError, "Can't insert left to root node."
      end
    end

    ##
    # Не меняя фокуса добавляет новый элемент правее элемента в фокусе.
    #
    #      ○            ○
    #     ╱ ╲         ╱ | ╲
    #    ○   ○  ⇀    ○  ○  ⊕
    #   ╱ ╲  ↑      ╱ ╲ ↑
    #  ○   ○       ○   ○
    #
    # @param [AST::Node, Object] new_node новый элемент
    # @return [AST::Zipper]
    #
    def insert_right( new_node )
      # Нельзя добавить элемент правее корневого элемент
      if not context.root?
        Zipper.new( value, context.alter(
          right_nodes: [ new_node ] + context.right_nodes,
          is_changed: true
        ))
      else
        raise ModificationError, "Can't insert right to root node."
      end
    end

    ##
    # Не меняя фокуса добавляет дочерний элемент в начало для элемента в фокусе.
    #
    #      ○            ○
    #     ╱ ╲          ╱ ╲
    #  → ○   ○  ⇀   → ○   ○
    #   ╱ ╲         ╱ | ╲
    #  ○    ○      ⊕  ○  ○
    #
    # @param [AST::Node, Object] new_node новый элемент
    # @return [AST::Zipper]
    #
    def append_child( new_node )
      # Нельзя добавить дочерние элементы для литералов
      if not literal?
        replace( value.append( new_node ))
      else
        raise ModificationError, "Can't append child to terminal node."
      end
    end

    ##
    # Не меняя фокуса добавляет дочерний элемент в конец для элемента в фокусе.
    #
    #      ○            ○
    #     ╱ ╲          ╱ ╲
    #  → ○   ○  ⇀   → ○   ○
    #   ╱ ╲         ╱ | ╲
    #  ○    ○      ○  ○  ⊕
    #
    # @param [AST::Node, Object] new_node новый элемент
    # @return [AST::Zipper]
    #
    def prepend_child( new_node )
      # Нельзя добавить дочерние элементы для литералов
      if not literal?
        replace( value.prepend( new_node ))
      else
        raise ModificationError, "Can't prepend child to terminal node."
      end
    end

    ##
    # Структура для хранения контекста (истории) обхода и модификации дерева.
    # При каждом переходе создаётся новый контекст, которы хранит ссылки на
    # родительский элемент, родительский контекст, элементы слева и элементы справа.
    # При изменении элемента выставляется флаг is_changed.
    #
    class Context
      # Ссылка на родителский контекст
      # @return [AST::Zipper::Context, nil]
      attr_reader :path

      # Ссылка на родительскую ноду
      # @return [AST::Node, nil]
      attr_reader :parent_node

      # Список элементов слева от текущего положения
      # @return [Array]
      attr_reader :left_nodes

      # Список справа слева от текущего положения
      # @return [Array]
      attr_reader :right_nodes

      # Флаг изменённости
      # @return [true, false]
      attr_reader :is_changed

      ##
      # Создаёт новый контекст. Объект заморожен!
      #
      def initialize( path: nil, parent_node: nil, left_nodes: [], right_nodes: [], is_changed: false )
        @path        = path.freeze
        @parent_node = parent_node.freeze
        @left_nodes  = left_nodes.freeze
        @right_nodes = right_nodes.freeze
        @is_changed  = is_changed.freeze
        self.freeze
      end

      ##
      # Возвращает копию контекста с заданными изменениями.
      #
      def alter( path: path, parent_node: parent_node, left_nodes: left_nodes, right_nodes: right_nodes, is_changed: is_changed )
        # NB: здесь имена параметров затеняют имена полей!
        self.class.new( path: path, parent_node: parent_node, left_nodes: left_nodes, right_nodes: right_nodes, is_changed: is_changed )
      end

      ##
      # Является контекст корневым?
      # @return [true, false]
      #
      def root?
        path == nil
      end
    end
  end
end

Зипперы из learnhaskell будут работать и для кастомных структур с кастомными маршрутами, можно попробовать какой-нибудь general вариант написать %)

Угу, надо в конструкторе передавать proc с алгоритмом получения детей и создания новой ноды.