2019-12-11 00:45 AEDT

View Issue Details Jump to Notes ]
IDProjectCategoryView StatusLast Update
0000207mercuryBugpublic2011-09-06 10:23
Reporterwangp 
Assigned Tozs 
PrioritynormalSeveritymajorReproducibilityalways
StatusresolvedResolutionfixed 
Product Version 
Target VersionFixed in Version 
Summary0000207: tree_bitset.difference bug
DescriptionIn the following test case tree_bitset.difference produces the wrong result on 32-bit platforms.

% ./tree_bitset_difference
set: [532, 32431]
tree_bitset: []

This affects the compiler since the recent representation change.
TagsNo tags attached.
Attached Files

-Relationships
+Relationships

-Notes

~0000342

zs (developer)

Fix committed 28 July.

~0000343

wangp (developer)

Unfortunately it was only a partial fix. Here are a few more cases. I don't know if there are significant differences between them.


    test([1, 29424], [1, 2, 3, 35701], !IO),
    test([1], [2, 35701], !IO),
    test([101, 102], [1, 2, 3, 35699, 35700, 35701], !IO),
    test([35696, 35702, 35703, 35704, 35705], [1, 2, 3, 33416, 334283], !IO),

~0000346

wangp (developer)

Last edited: 2011-08-03 12:17

Is this the fix? edit: no.

diff --git a/library/tree_bitset.m b/library/tree_bitset.m
index e01831c..716416f 100644
--- a/library/tree_bitset.m
+++ b/library/tree_bitset.m
@@ -2130,7 +2130,7 @@ difference(SetA, SetB) = Set :-
 interiornode_difference(LevelA, HeadA, TailA, LevelB, HeadB, TailB,
         Level, List) :-
     ( LevelA < LevelB ->
- range_of_parent_node(HeadA ^ init_offset, LevelA + 1,
+ range_of_parent_node(HeadA ^ init_offset, LevelA,
             ParentInitOffsetA, ParentLimitOffsetA),
         (
             find_containing_node(ParentInitOffsetA, ParentLimitOffsetA,

~0000347

zs (developer)

That fixes one bug, but there are others. I have tentative fixes for another two, but I am reconsidering the wisdom of just fixing bugs in the existing code. The code was designed the way it is because it was supposed to be slow but simple, and the bugs show it isn't simple. It looks like getting a faster design correct may not be that much more work than fixing the slow design.

In the meantime, one possible workaround for the problem is to make set_of_var use sparse_bitset instead of tree_bitset.

~0000359

zs (developer)

Fix committed a while ago.
+Notes

-Issue History
Date Modified Username Field Change
2011-07-28 10:49 wangp New Issue
2011-07-28 10:49 wangp File Added: tree_bitset_difference.m
2011-07-28 10:50 wangp Status new => assigned
2011-07-28 10:50 wangp Assigned To => zs
2011-07-28 14:53 zs Note Added: 0000342
2011-07-28 14:53 zs Status assigned => resolved
2011-07-28 14:53 zs Resolution open => fixed
2011-07-29 10:13 wangp Note Added: 0000343
2011-07-29 10:13 wangp Status resolved => feedback
2011-07-29 10:13 wangp Resolution fixed => reopened
2011-08-02 14:52 wangp Note Added: 0000345
2011-08-02 15:38 wangp Note Deleted: 0000345
2011-08-03 12:07 wangp Note Added: 0000346
2011-08-03 12:07 wangp Status feedback => assigned
2011-08-03 12:17 wangp Note Edited: 0000346
2011-08-03 19:16 zs Note Added: 0000347
2011-09-06 10:23 zs Note Added: 0000359
2011-09-06 10:23 zs Status assigned => resolved
2011-09-06 10:23 zs Resolution reopened => fixed
+Issue History