[redland-dev] [Raptor RDF Syntax Library 0000455]: Incorrect AVL tree operations. [ with fix ]

[Mantis Bug Tracker]

The following issue has been SUBMITTED. 
====================================================================== 
http://bugs.librdf.org/mantis/view.php?id=455 
====================================================================== 
Reported By:                v-for-vandal
Assigned To:                
====================================================================== 
Project:                    Raptor RDF Syntax Library
Issue ID:                   455
Category:                   api
Reproducibility:            always
Severity:                   major
Priority:                   normal
Status:                     new
Syntax Name:                TRiG 
====================================================================== 
Date Submitted:             2011-07-14 13:32
Last Modified:              2011-07-14 13:32
====================================================================== 
Summary:                    Incorrect AVL tree operations. [ with fix ]
Description: 
When removing node, the 'parent' field of the child nodes of the removed one is
not updated.
This lead to  hardly-catchable bugs.



Steps to Reproduce: 
Compile raptor with -DRAPTOR_DEBUG=5 -DRAPTOR_MEMORY_SIGN. Then run it over
nao.trig file ( or over attached test ) several times. Most of them should fail
( in my case - all did ).

Error may be easier to catch if you apply raptor_detect_error.diff. This patch
adds raptor_avltree_check before and after body of  every function
adding/removing node. It alsa extends raptor_avltree_check_node with one more
usefull check. After applying patch and compiling with mentioned above flags,
run 'rapper -i trig -o rdfxml nao2.trig' several times. Most should fail. File
"nao2.trig" is attached. It has incorrect syntax, but that doesn't matter.

Additional Information: 
Howto fix: Unfortunatelly, patch to fix this error is merged with patch to
detect an error and I don't know how to split them. I will simply post new code
here:

starting from line approx 785, function raptor_avltree_delete_internal near the
end

raptor_avltree_node *pr_q;
      
    RAPTOR_AVLTREE_DEBUG1("equal\n");
    pr_q = *node_pp;

    rdata = pr_q->data;

    if(pr_q->right == NULL) {
      RAPTOR_AVLTREE_DEBUG1("right subtree null\n");
      *node_pp = pr_q->left;
      // Change code here - update parent
      if ( pr_q->left)
          pr_q->left->parent = pr_q->parent;
      // End of change^^
      *rebalancing_p = TRUE;
    } else if(pr_q->left == NULL) {
      RAPTOR_AVLTREE_DEBUG1("right subtree non-null, left subtree null\n");
      *node_pp = pr_q->right;
      // Same change here - update parent
      if ( pr_q->right)
          pr_q->right->parent = pr_q->parent;
      *rebalancing_p = TRUE;
    } else {


And in function raptor_avltree_delete_internal2

} else {
    rdata = (*ppr_q)->data;

    (*ppr_q)->data = (*ppr_r)->data;
    *ppr_q = *ppr_r;
    // change code here - remeber parent
    raptor_avltree_node * ppr_r_left_new_parent = (*ppr_r)->parent;
    *ppr_r = (*ppr_r)->left;
    // and if right do exist, update it's parent
    if ( *ppr_r )
        (*ppr_r)->parent = ppr_r_left_new_parent;
    // End of change ^^
    *rebalancing_p = TRUE;
  }

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

Issue History 
Date Modified    Username       Field                    Change               
====================================================================== 
2011-07-14 13:32 v-for-vandal   New Issue                                    
2011-07-14 13:32 v-for-vandal   File Added: nao2.trig                        
======================================================================