def walk_rec(hlir, parse_state, prev_hdr_node, tag_stacks_index, visited,
                 recursion_states):
        assert(isinstance(parse_state, p4.p4_parse_state))
        rec_state = State(parse_state, prev_hdr_node, tag_stacks_index)
        if rec_state in recursion_states:
            return
        recursion_states.add(rec_state)
        for call in parse_state.call_sequence:
            call_type = call[0]
            if call_type == p4.parse_call.extract:
                hdr = call[1]

                if hdr.virtual:
                    base_name = hdr.base_name
                    current_index = tag_stacks_index[base_name]
                    if current_index > hdr.max_index:
                        return
                    tag_stacks_index[base_name] += 1
                    name = base_name + "[%d]" % current_index
                    hdr = hlir.p4_header_instances[name]
                # takes care of loops in parser (e.g. for TLV parsing)
                elif parse_state in visited:
                    return

                if hdr not in header_graph:
                    header_graph.add_node(hdr)
                hdr_node = header_graph.get_node(hdr)

                if prev_hdr_node:
                    prev_hdr_node.add_edge_to(hdr_node)
                else:
                    header_graph.root = hdr
                prev_hdr_node = hdr_node

        for branch_case, next_state in parse_state.branch_to.items():
            if not next_state:
                continue
            if not isinstance(next_state, p4.p4_parse_state):
                continue
            walk_rec(hlir, next_state, prev_hdr_node,
                     tag_stacks_index.copy(), visited | {parse_state},
                     recursion_states)