Fix infinite loop in ncplane_move_family_*

[drewt]

When moving a plane-family up in z-order with ncplane_move_family above (or down with ncplane_move_family_below), the first loop does not terminate. It iterates past n and then repeatedly moves its descendants above/below each other forever.

This is fixed by terminating the loop if it reaches n.

[dankamongmen]

AWESOME! i'd love to have a unit test on this, but understood if you're not interested in making one. this logic is sufficiently complex, however, that i feel a unit test is due, so maybe i can put one together?

if i haven't merged this in a few days (or otherwise replied), please ping me. thanks a lot for digging into this and coming up with a solution! your comment sounds competent enough that i imagine this is correct. =]

[dankamongmen]

alright, sorry for the delay here. i've finally got some time tonight to make the corresponding unit test, and then merge this. thanks so much!

[dankamongmen]

ok, reproduced the infinite loop with a new unit test...

[dankamongmen]

  // contributed by drewt on github, this led to an infinite loop
  SUBCASE("FamilyAbove") {
    ncplane_options nopts{};
    nopts.rows = 1;
    nopts.cols = 1;
    struct ncplane *n = ncplane_create(notcurses_stdplane(nc_), &nopts);
    struct ncplane *a = ncplane_create(n, &nopts);
    struct ncplane *b = ncplane_create(n, &nopts);
    struct ncplane *bpoint = ncplane_create(notcurses_stdplane(nc_), &nopts);
    ncplane_move_family_above(n, bpoint);
    ncplane_destroy(bpoint);
    ncplane_destroy(b);
    ncplane_destroy(a);
    ncplane_destroy(n);
  }

[dankamongmen]

FAMILY ABOVE*******************************
MOVING 0x559a2d4da010 above 0x559a2d4d9f20
 -------------------------- notcurses debug state -----------------------------
  *************************   0x559a2d4d7680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x559a2d4da010 
 bound 0x559a2d4d7590 ← 0x559a2d4d9f80 → (nil) binds 0x559a2d4da1f0
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x559a2d4d9f20 
 bound 0x559a2d4d7590 ← 0x559a2d4d7600 → 0x559a2d4da010 binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x559a2d4da1f0 
 bound 0x559a2d4da010 ← 0x559a2d4da080 → 0x559a2d506900 binds (nil)
0003 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x559a2d506900 
 bound 0x559a2d4da010 ← 0x559a2d4da250 → (nil) binds (nil)
0004 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x559a2d4d7590 std
 bound 0x559a2d4d7590 ← 0x559a2d4d7690 → (nil) binds 0x559a2d4d9f20
 ______________________________________________________________________________

[dankamongmen]

FAMILY ABOVE*******************************
MOVING 0x5608e32cc010 above 0x5608e32cbf20
 -------------------------- notcurses debug state -----------------------------
  *************************   0x5608e32c9680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cbf20 
 bound 0x5608e32c9590 ← 0x5608e32c9600 → 0x5608e32cc010 binds (nil)
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cc1f0 
 bound 0x5608e32cc010 ← 0x5608e32cc080 → 0x5608e32f8900 binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32f8900 
 bound 0x5608e32cc010 ← 0x5608e32cc250 → (nil) binds (nil)
0003 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cc010 
 bound 0x5608e32c9590 ← 0x5608e32cbf80 → (nil) binds 0x5608e32cc1f0ta/ --test-case=ZAxis 
0004 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x5608e32c9590 std
 bound 0x5608e32c9590 ← 0x5608e32c9690 → (nil) binds 0x5608e32cbf20
 ______________________________________________________________________________
 -------------------------- notcurses debug state -----------------------------
  *************************   0x5608e32c9680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cc010 
 bound 0x5608e32c9590 ← 0x5608e32cbf80 → (nil) binds 0x5608e32cc1f0
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cbf20 
 bound 0x5608e32c9590 ← 0x5608e32c9600 → 0x5608e32cc010 binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32cc1f0 
 bound 0x5608e32cc010 ← 0x5608e32cc080 → 0x5608e32f8900 binds (nil)
0003 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5608e32f8900 
 bound 0x5608e32cc010 ← 0x5608e32cc250 → (nil) binds (nil)
0004 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x5608e32c9590 std
 bound 0x5608e32c9590 ← 0x5608e32c9690 → (nil) binds 0x5608e32cbf20
 ______________________________________________________________________________

[dankamongmen]

FAMILY ABOVE*******************************
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds (nil)
 ______________________________________________________________________________
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 pp.o
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → (nil) binds (nil)
0001 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds 0x558a5b2df010ta/ --test-case=ZAxis 
 ______________________________________________________________________________
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b30b900 
 bound 0x558a5b2df010 ← 0x558a5b2df080 → (nil) binds (nil)
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → (nil) binds 0x558a5b30b900
0002 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds 0x558a5b2df010
 ______________________________________________________________________________
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df1f0 
 bound 0x558a5b2df010 ← 0x558a5b2df080 → 0x558a5b30b900 binds (nil)
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b30b900 
 bound 0x558a5b2df010 ← 0x558a5b2df250 → (nil) binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → (nil) binds 0x558a5b2df1f0
0003 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds 0x558a5b2df010
 ______________________________________________________________________________
MOVING 0x558a5b2df010 above 0x558a5b2def20
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2def20 
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → 0x558a5b2df010 binds (nil)
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df1f0 
 bound 0x558a5b2df010 ← 0x558a5b2df080 → 0x558a5b30b900 binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b30b900 
 bound 0x558a5b2df010 ← 0x558a5b2df250 → (nil) binds (nil)
0003 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 
 bound 0x558a5b2dc590 ← 0x558a5b2def80 → (nil) binds 0x558a5b2df1f0
0004 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds 0x558a5b2def20
 ______________________________________________________________________________
 -------------------------- notcurses debug state -----------------------------
  *************************   0x558a5b2dc680 pile ****************************
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 
 bound 0x558a5b2dc590 ← 0x558a5b2def80 → (nil) binds 0x558a5b2df1f0
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2def20 
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → 0x558a5b2df010 binds (nil)
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df1f0 
 bound 0x558a5b2df010 ← 0x558a5b2df080 → 0x558a5b30b900 binds (nil)
0003 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b30b900 
 bound 0x558a5b2df010 ← 0x558a5b2df250 → (nil) binds (nil)
0004 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x558a5b2dc590 std
 bound 0x558a5b2dc590 ← 0x558a5b2dc690 → (nil) binds 0x558a5b2def20
 ______________________________________________________________________________

[dankamongmen]

above: 0x558a5b2dc590

so in that last debug output, we've got:

0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2df010 
 bound 0x558a5b2dc590 ← 0x558a5b2def80 → (nil) binds 0x558a5b2df1f0
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x558a5b2def20 
 bound 0x558a5b2dc590 ← 0x558a5b2dc600 → 0x558a5b2df010 binds (nil)

but we were trying to move 0x558a5b2df010 above 0x558a5b2def20...but it's below 0x558a5b2def20 following ncplane_move_above(). which seems definitely wrong, and points to a bug in ncplane_move_above().

[dankamongmen]

yeah we're definitely fucking up in ncplane_move_above(). again, i don't think your fix ought be necessary @drewt if all our postconditions are valid. this does not appear to be the case based on the notcurses_debug() output above. i'm looking for the true fix.

does this jive with your understanding? you wrote:

Then ncplane_move_above moves n to the end. above still points to a:

so (1) ncplane_move_above() ought be putting it in the penultimate position, not the last one (you'd want ncplane_move_above(n, NULL) to put it at the bottom), and (2) if ncplane_move_above() has a bug, that explodes your analysis here, right?

[dankamongmen]

    SPLICE OUT 0x5586ff8f6c10                                                                                                       
 -------------------------- notcurses debug state -----------------------------                                                     
  *************************   0x5586ff8f4280 pile ****************************                                                      
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5586ff8f6b20                                                         
 bound 0x5586ff8f4190 ← 0x5586ff8f4200 → 0x5586ff8f6c10 binds (nil)           <------ f6c10 is spliced out of z, but is still on blist...is this a problem?                                                      
0001 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5586ff8f6df0                                                         
 bound 0x5586ff8f6c10 ← 0x5586ff8f6c80 → 0x5586ff923500 binds (nil)                                                                 
0002 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x5586ff923500                                                         
 bound 0x5586ff8f6c10 ← 0x5586ff8f6e50 → (nil) binds (nil)                                                                          
0003 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x5586ff8f4190 std                                                     
 bound 0x5586ff8f4190 ← 0x5586ff8f4290 → (nil) binds 0x5586ff8f6b20                                                                 
 ______________________________________________________________________________                                                     
    SPLICED OUT 0x5586ff8f6c10                                                                                                      

[dankamongmen]

 -------------------------- notcurses debug state -----------------------------                                                     
  *************************   0x55a6b4f52280 pile ****************************                                                      
0000 off y:   0 x:   0 geom y:   1 x:   1 curs y:   0 x:   0 0x55a6b4f54c10                                                         
 bound 0x55a6b4f52190 ← 0x55a6b4f54b80 → (nil) binds 0x55a6b4f54df0                                                                 
0001 off y:   0 x:   0 geom y:  64 x: 132 curs y:   0 x:   0 0x55a6b4f52190 std                                                     
 bound 0x55a6b4f52190 ← 0x55a6b4f52290 → (nil) binds 0x55a6b4f54b20                                                                 
 WARNING: expected ->above 0x55a6b4f54c10, got 0x55a6b4f81500                                                                       
 ______________________________________________________________________________   

this is after we've set n->above to splice it back in. this looks wrong. n->below is NULL as expected, but n->above is pointing at the standard plane, and the standard plane thinks n is underneath it...? unless i'm reading this incorrectly?

[dankamongmen]

is above->above possibly wrong? checking!

[dankamongmen]

it looks like it might be NULL? that wouldn't be right! wouldn't that get a warning in notcurses_debug(), though?

[dankamongmen]

    SPLICED OUT 0x559366a00c10                                                                                                      
ABOVE->ABOVE: (nil)                                                                                                                 
IT WAS NULL!        

so yeah, it definitely looks like we have an invalid above field in the target (the bottom plane). due to this, we insert n back at p->top, from which all these other miseries emerge, and that's how we get a cycle on the zaxis.

so there's our real bug. bpoint->above appears to be NULL going into at least ncplane_move_family_above(). let me figure out how that is happening, and we'll have a true fix. thanks for finding this real problem, @drewt ! i will fix this, and it will fix your case, i'm certain.

[dankamongmen]

we indeed ought have been getting a warning about this in ncpile_debug(), it seems:

    if(n->above != prev){                                                                                                           
      fbuf_printf(f, " WARNING: expected ->above %p, got %p\n", prev, n->above);                                                    
    }                             

[dankamongmen]

confirmed:

===============================================================================
/home/dank/src/dankamongmen/notcurses/src/tests/zaxis.cpp:5:
TEST CASE:  ZAxis
  FamilyAbove

/home/dank/src/dankamongmen/notcurses/src/tests/zaxis.cpp:255: FATAL ERROR: REQUIRE( bpoint->above ) is NOT correct!
  values: REQUIRE( nullptr )

==================================================================

why on earth aren't we getting a warning?

[dankamongmen]

wait, have i been misreading these stacks the entire time? is it top-to-bottom and not bottom-to-top? that would make more sense. lol

[dankamongmen]

yeah, embarrassing, whoops!

alright, well we can ignore all of that, then.

[dankamongmen]

so we're taking the next-to-bottom and moving it to the top, got it. let's check and see whether we break the same way calling trhough ncplane_move_to_top()....NO, that succeeds rather than hitting an infinite loop. it is:

__attribute__ ((nonnull (1)))                                                                                                       
static inline void                                                                                                                  
ncplane_move_family_top(struct ncplane* n){                                                                                         
  ncplane_move_family_below(n, NULL);                                                                                               
}                

interesting, do we expect ncplane_move_family_below(n, NULL) to be the same as ncplane_move_family_above(n, [top plane of pile])? i would think so?

[dankamongmen]

so looking at these dumps correctly, we now have n above bpoint, which is exactly what we want.

ok, i think your analysis is correct, and will be merging your original fix. =]