global

def match(ast, matcher)
  return false if ast.nil?
  ast_parts = [ast.type] + ast.children
  self_parts = [type] + children
  return false if ast_parts.length != self_parts.length
  ast_parts.length.times.all? do |i|
    ast_elem = ast_parts[i]
    self_elem = self_parts[i]
    if self_elem.is_a?(Node) && self_elem.type == :capture
      capture = true
      self_elem = self_elem.children.first
    end
    res = case self_elem
          when Node
            self_elem.match(ast_elem, matcher)
          when Array
            self_elem.include?(ast_elem)
          when :*
            true
          else
            self_elem == ast_elem
          end
    matcher.captures << ast_elem if capture
    res
  end
end