aboutsummaryrefslogblamecommitdiffstats
path: root/actionpack/lib/action_dispatch/journey/gtg/builder.rb
blob: 450588cda69087f900f7321ad8c60a971d76718d (plain) (tree)
1
2
3
4
5
6
7
8
9
10


                                                      



                                


                                           



                                                 














                                                                  
                                                  






                                           

                                                                   


                                                      
                                    

                                  
                                                                              

                                                    
                                                             

                   
                                                   









                          
                           











                                                         
                                




                                                                         
                          



                               
                                   




                                                        
                                                           








                                                                         
                         



                               
                                                          
                         
                                    












                                                                        
                           



                               
 















                                                 

                 
                 
             
 






                                       
             



         
require 'action_dispatch/journey/gtg/transition_table'

module ActionDispatch
  module Journey # :nodoc:
    module GTG # :nodoc:
      class Builder # :nodoc:
        DUMMY = Nodes::Dummy.new

        attr_reader :root, :ast, :endpoints

        def initialize(root)
          @root      = root
          @ast       = Nodes::Cat.new root, DUMMY
          @followpos = nil
        end

        def transition_table
          dtrans   = TransitionTable.new
          marked   = {}
          state_id = Hash.new { |h,k| h[k] = h.length }

          start   = firstpos(root)
          dstates = [start]
          until dstates.empty?
            s = dstates.shift
            next if marked[s]
            marked[s] = true # mark s

            s.group_by { |state| symbol(state) }.each do |sym, ps|
              u = ps.flat_map { |l| followpos(l) }
              next if u.empty?

              if u.uniq == [DUMMY]
                from = state_id[s]
                to   = state_id[Object.new]
                dtrans[from, to] = sym

                dtrans.add_accepting(to)
                ps.each { |state| dtrans.add_memo(to, state.memo) }
              else
                dtrans[state_id[s], state_id[u]] = sym

                if u.include?(DUMMY)
                  to = state_id[u]

                  accepting = ps.find_all { |l| followpos(l).include?(DUMMY) }

                  accepting.each { |accepting_state|
                    dtrans.add_memo(to, accepting_state.memo)
                  }

                  dtrans.add_accepting(state_id[u])
                end
              end

              dstates << u
            end
          end

          dtrans
        end

        def nullable?(node)
          case node
          when Nodes::Group
            true
          when Nodes::Star
            true
          when Nodes::Or
            node.children.any? { |c| nullable?(c) }
          when Nodes::Cat
            nullable?(node.left) && nullable?(node.right)
          when Nodes::Terminal
            !node.left
          when Nodes::Unary
            nullable?(node.left)
          else
            raise ArgumentError, 'unknown nullable: %s' % node.class.name
          end
        end

        def firstpos(node)
          case node
          when Nodes::Star
            firstpos(node.left)
          when Nodes::Cat
            if nullable?(node.left)
              firstpos(node.left) | firstpos(node.right)
            else
              firstpos(node.left)
            end
          when Nodes::Or
            node.children.flat_map { |c| firstpos(c) }.uniq
          when Nodes::Unary
            firstpos(node.left)
          when Nodes::Terminal
            nullable?(node) ? [] : [node]
          else
            raise ArgumentError, 'unknown firstpos: %s' % node.class.name
          end
        end

        def lastpos(node)
          case node
          when Nodes::Star
            firstpos(node.left)
          when Nodes::Or
            node.children.flat_map { |c| lastpos(c) }.uniq
          when Nodes::Cat
            if nullable?(node.right)
              lastpos(node.left) | lastpos(node.right)
            else
              lastpos(node.right)
            end
          when Nodes::Terminal
            nullable?(node) ? [] : [node]
          when Nodes::Unary
            lastpos(node.left)
          else
            raise ArgumentError, 'unknown lastpos: %s' % node.class.name
          end
        end

        def followpos(node)
          followpos_table[node]
        end

        private

          def followpos_table
            @followpos ||= build_followpos
          end

          def build_followpos
            table = Hash.new { |h, k| h[k] = [] }
            @ast.each do |n|
              case n
              when Nodes::Cat
                lastpos(n.left).each do |i|
                  table[i] += firstpos(n.right)
                end
              when Nodes::Star
                lastpos(n).each do |i|
                  table[i] += firstpos(n)
                end
              end
            end
            table
          end

          def symbol(edge)
            case edge
            when Journey::Nodes::Symbol
              edge.regexp
            else
              edge.left
            end
          end
      end
    end
  end
end