marvin at rectangular
Apr 2, 2007, 2:47 PM
Post #15 of 18
(1281 views)
Permalink
|
On Mar 31, 2007, at 11:29 PM, Chris Nandor wrote:
> I think I got all of your suggestions in this patch:
>
> * PolyFilter->bits() returns undef if add() not called,
> make_collector()
> returns $inner_coll if bits() returns undef
>
> * poly_filter.t tests no calls to add(), and each possibility of
> single
> calls to add()
I found a glitch in this test group: AND was being tested three
times, instead of AND, OR, and XOR. No bugs revealed in the module
code once the test glitch was fixed, though. :)
> * Behavior is different if first call to add() has logic => 'NOT'
I've applied your patch, with the small mod above, as revision 2249.
I believe we can now declare PolyFilter functional. Thank you, and
hooray!
> For the latter, I added a new C method BitVec_invert, which inverts
> every
> bit, which has the effect of a single-input logical NOT.
A big ol' grin stole across my face when I read that, and it got
wider as I perused the patch itself. You nailed every aspect of the
integration (though BitVec_Invert is problematic for subtle
reasons). I'm curious how challenging you found it to grok how to
add your C/XS code.
The thing about BitVec_Invert as implemented in the patch, though, is
that it can flip some bits we don't want flipped. Here's a failing
test I wrote for it:
$bit_vec = KinoSearch::Util::BitVector->new( capacity => 5 );
$bit_vec->set( 1 .. 4 );
$bit_vec->invert; # flips bits 0 .. 7
$bit_vec->set(10); # cap now 11, exposing previously hidden bits
ok( !$bit_vec->get(7),
"invert doesn't set bits outside of valid range" );
BitVector's "cap" variable is an internal number for keeping track of
allocations. It's just there to make sure we never access invalid
memory. It's not the logical size of the bitVector.
In the test above, Invert() flips bits beyond cap -- bits 5, 6, and 7
-- because it does byte-at-a-time bit-flipping. You don't notice
that right away, but after the BitVector grows (which can happen for
a variety of reasons, including BitVec->set with a number greater
than the current cap, as above), those messed up bits get exposed.
That flaw wasn't affecting PolyFilter at present, but that was only
because those cached BitVector objects coincidentally never grow.
The bug needed to be fixed lest it induce some bizarre buggy behavior
somewhere down the line.
The solution was to refactor BitVec_Invert into BitVec_Flip_Range,
and have it take two arguments: from_bit and to_bit. The interface
is roughly based upon java.util.BitSet, as is much of the rest of
BitVector's API.
Flip_Range() is more appropriate because a BitVector doesn't really
have an explicit length, like a Perl array does. Logically, it's a
set of numbers, as determined by the indexes of all bits which are
1. You can't invert "all the elements", because "all the elements"
means "all positive integers", if it means anything at all.
Similar problems were actually afflicting OR, XOR, and BitVec_Count,
but they would have arisen under even more subtle circumstances. I
believe I have everything sorted now, as of commit 2252; I'm glad
that BitVec_Invert brought the problems to my attention.
This was somewhat all somewhat more laborious to work out than I'd
thought it would be; sorry about the delay in responding to your patch.
Marvin Humphrey
Rectangular Research
http://www.rectangular.com/
|
