Find opcode's reverse sibling?

diotalevi has asked for the wisdom of the Perl Monks concerning the following question:

Is there a more straightforward way to find $op_A where $op_A->sibling( $op_B ) when you have $op_B? I have B::Utils and B::Generate loaded. I am not using ->kids because it avoids null nodes but sometimes the node being searched from is a null node.

# Maybe find the opcode that thinks this opcode is its sibling by
# going to this opcode's parent and walking over the list of siblings
# until this one is reached. The previously visited opcode is the one
# we're after.
my $orig_reverse_sibling;
{
    my $prev;
    for ( my $sibling = $op->parent->first;
          $sibling;
          $sibling = $sibling->sibling )
    {
        if ( $sibling == $op )
        {
            $orig_reverse_sibling = $prev;
            last;
        }
        else
        {
            $prev = $sibling;
        }
    }
}
[download]

Comment on Find opcode's reverse sibling? Download Code

Replies are listed 'Best First'.
Re: Find opcode's reverse sibling? by andyf (Pilgrim) on Jun 12, 2004 at 18:59 UTC
Can you elaborate please Diotalevi. Some modern tree math terminology (badly) refers to 'siblings' and 'children' the same. You want to find to all nodes that share the same parent? That is what siblings are. If so the method you have, traverse to the parent and enumerate all children is optimal. In a B-Tree there will only be 2 possible children, so just the fact of having more than one link tells you a sibling exists. Node depth alone is not enough, it could be the evil twin on the other side of the tree.	[reply]
Re^2: Find opcode's reverse sibling? by diotalevi (Canon) on Jun 13, 2004 at 12:10 UTC
You're on the wrong track. These terms are specific to perl's internal representation of compiled perl code. Here, children and siblings are separete things - siblings is a ordered, linked list of nodes that are children to a parent node. The linked list is constituted by a op_sibling pointer, the parent points to the first sibling with op_first, the last sibling with op_last and none of the middle ones. Sibling nodes do not point at any other sibling nodes except with the previously described op_sibling pointer. This is all about perl guts.	[reply]
Re: Find opcode's reverse sibling? by Mr. Muskrat (Canon) on Jun 12, 2004 at 19:19 UTC
I think what diotalevi is trying to acheive is the reverse of B's `next` method, a new `previous` method. Yes? If so, then I think that your snippet would be fine (although I don't muck around with the B modules much).	[reply]
Re^2: Find opcode's reverse sibling? by dave_the_m (Monsignor) on Jun 12, 2004 at 22:16 UTC
I think what diotalevi is trying to acheive is the reverse of B's next method Er, no. Siblings and next are two different things. Siblings are a chain of ops at the same level in a tree; next is the next op in execution sequence. For example $ perl584 -MO=Concise -e'print "a", $b+1;' 9 <@> leave[1 ref] vKP/REFC ->(end) 1 <0> enter ->2 2 <;> nextstate(main 1 -e:1) v ->3 8 <@> print vK ->9 3 <0> pushmark s ->4 4 <$> const(PV "a") s ->5 7 <2> add[t1] sK/2 ->8 - <1> ex-rv2sv sK/1 ->6 5 <$> gvsv(b) s ->6 6 <$> const(IV 1) s ->7 $ perl584 -MO=Concise,-exec -e'print "a", $b+1;' 1 <0> enter 2 <;> nextstate(main 1 -e:1) v 3 <0> pushmark s 4 <$> const(PV "a") s 5 <$> gvsv(b) s 6 <$> const(IV 1) s 7 <2> add[t1] sK/2 8 <@> print vK 9 <@> leave[1 ref] vKP/REFC [download] Here, the first child of print is pushmark, and const and add are the two siblings of pushmark. On the other hand, print's next op is leave. Internally Perl doesn't store pointers to previous siblings, not does it store a pointer to the parent. So my initial reaction is that the OP's approach is correct. However, since the B modules provide a parent() method when internally there is no such pointer, it's posssible that B:;* can do other clever stuff too. I've never looked at it myself. Dave.	[reply] [d/l]
Re^3: Find opcode's reverse sibling? by Mr. Muskrat (Canon) on Jun 13, 2004 at 01:36 UTC
That just goes to show how little I really know about B. I thought if you had stored a child op that you could use `next` on it to get the next sibling. Hence my comment about reversing it to create a `previous` method. Looks like I'll need to reread that stuff again. :)	[reply]