search

rudi / redmine-test

Test migration of redmine issues
0 stars 0 forks source link

Buggy Set implementation in ABS standard library #72

Open rudi opened 8 years ago

rudi commented 8 years ago

Author Name: Nikolaos Bezirgiannis (@bezirg) Original Redmine Issue: 112, https://envisage.ifi.uio.no:8080/redmine/issues/112 Original Date: 2014-01-20 Original Assignee: Rudolf Schlatte

The size implementation of the Set datastructure in the ABS standard library is wrong.

Consider this code:

{ Set s = set[4,4,4]; assert (size(s) == 1);

}

This assertion fails. Where this assertion succeeds:

{ Set s = set[4,4,4]; assert (size(s) == 3);

}

The problem lies in abslang.abs . The size function acts more like a list length function and does not pay respect to duplicate items.

Also, IMO both Set and Map datastructures should better be implemented for efficiency reasons as balanced binary trees, and not as simple lists (Set) and association lists (Map).

Nikolaos

rudi commented 8 years ago

Original Redmine Comment Author Name: Volker Stolz (@VolkerStolz) Original Date: 2014-01-20T10:45:25Z

It'd be great if you can directly add the unit tests!

rudi commented 8 years ago

Original Redmine Comment Author Name: Rudolf Schlatte (@rudi) Original Date: 2014-01-20T10:47:14Z

Agreed on both counts. Note also that the current implementation is buggy wrt equality (==) because its internal representation is sensitive to insertion order.

Now that we have a general less-than operator, set can be reimplemented as a tree -- but existing code will break since the constructor names will change.

rudi commented 8 years ago

Original Redmine Comment Author Name: Rudolf Schlatte (@rudi) Original Date: 2014-02-17T11:52:21Z

Fixed in 834a3c6; I went with a sorted list implementation for now. Note that any tree structure implementing sets needs to be invariant wrt insertion order, or we have to forbid s1 == s2 for sets.