Fix two bugs in hb_set_is_subset(). 1. If smaller set has empty pages the subset checking logic was incorrectly incrementing the larger page index after skipping the empty smaller page index. 2. The logic for is_subset() on mixed inverted/not inverted sets was wrong.
diff --git a/src/hb-bit-set-invertible.hh b/src/hb-bit-set-invertible.hh index c244316..48b2e21 100644 --- a/src/hb-bit-set-invertible.hh +++ b/src/hb-bit-set-invertible.hh
@@ -173,7 +173,14 @@ bool is_subset (const hb_bit_set_invertible_t &larger_set) const { if (unlikely (inverted != larger_set.inverted)) - return hb_all (hb_iter (s) | hb_map (larger_set.s)); + { + if (inverted) + return hb_all (iter (), larger_set.s); + else + // larger set is inverted so larger_set.s is the set of things that are not present + // in larger_set, therefore if s has any of those it can't be a subset. + return !s.intersects (larger_set.s); + } else return unlikely (inverted) ? larger_set.s.is_subset (s) : s.is_subset (larger_set.s); }
diff --git a/src/hb-bit-set.hh b/src/hb-bit-set.hh index db21477..0572504 100644 --- a/src/hb-bit-set.hh +++ b/src/hb-bit-set.hh
@@ -438,23 +438,31 @@ return false; uint32_t spi = 0; - for (uint32_t lpi = 0; spi < page_map.length && lpi < larger_set.page_map.length; lpi++) + uint32_t lpi = 0; + while (spi < page_map.length && lpi < larger_set.page_map.length) { uint32_t spm = page_map.arrayZ[spi].major; uint32_t lpm = larger_set.page_map.arrayZ[lpi].major; auto sp = page_at (spi); - if (spm < lpm && !sp.is_empty ()) - return false; - - if (lpm < spm) + if (spm < lpm) { + if (!sp.is_empty ()) + return false; + spi++; continue; + } + + if (lpm < spm) { + lpi++; + continue; + } auto lp = larger_set.page_at (lpi); if (!sp.is_subset (lp)) return false; spi++; + lpi++; } while (spi < page_map.length)
diff --git a/test/api/test-set.c b/test/api/test-set.c index b83cc55..077d634 100644 --- a/test/api/test-set.c +++ b/test/api/test-set.c
@@ -25,6 +25,7 @@ */ #include "hb-test.h" +#include "hb.h" /* Unit tests for hb-set.h */ @@ -268,6 +269,90 @@ } static void +test_set_subsets_empty_pages (void) +{ + hb_set_t *s = hb_set_create (); + hb_set_t *l = hb_set_create (); + hb_set_add (s, 0x00F); + hb_set_add (s, 0xFFF); + hb_set_del (s, 0x00F); + + hb_set_add (l, 0xFFF); + + g_assert_true (hb_set_is_subset (s, l)); + g_assert_true (hb_set_is_subset (l, s)); + + hb_set_destroy (s); + hb_set_destroy (l); + + s = hb_set_create (); + l = hb_set_create (); + hb_set_add (s, 0xFFF); + hb_set_add (s, 0x00F); + hb_set_del (s, 0xFFF); + + hb_set_add (l, 0x00F); + + g_assert_true (hb_set_is_subset (s, l)); + g_assert_true (hb_set_is_subset (l, s)); + + hb_set_destroy (s); + hb_set_destroy (l); +} + +static void +test_set_subsets_inverted (void) +{ + hb_set_t *s = hb_set_create (); + hb_set_t *l = hb_set_create (); + + hb_set_add (s, 1); + hb_set_add (l, 1); + hb_set_invert (l); + + // s contains {1}. + // l contains everything except {1}. + // s should not be a subset of l. + g_assert_true (!hb_set_is_subset (s, l)); + + hb_set_clear (s); + hb_set_add (s, 2); + // s contains {2}. + // l contains everything except {1}. + // s should be a subset of l. + g_assert_true (hb_set_is_subset (s, l)); + + hb_set_invert (s); + // s contains everything except {2}. + // l contains everything except {1}. + // s is not a subset of l. + g_assert_true (!hb_set_is_subset (s, l)); + + hb_set_clear (s); + hb_set_add (s, 1); + hb_set_add (s, 2); + hb_set_invert (s); + // s contains everything except {1, 2}. + // l contains everything except {1}. + // s should be a subset of l. + g_assert_true (hb_set_is_subset (s, l)); + + hb_set_clear (s); + hb_set_clear (l); + hb_set_invert(s); + hb_set_add (l, 0); + hb_set_add (l, 1); + hb_set_add (l, 2); + // s contains everything except + // l contains {0, 1, 2}. + // s should not be a subset of l. + g_assert_true (!hb_set_is_subset (s, l)); + + hb_set_destroy (s); + hb_set_destroy (l); +} + +static void test_set_algebra (void) { hb_set_t *s = hb_set_create (); @@ -1199,6 +1284,8 @@ hb_test_add (test_set_basic); hb_test_add (test_set_subsets); + hb_test_add (test_set_subsets_empty_pages); + hb_test_add (test_set_subsets_inverted); hb_test_add (test_set_algebra); hb_test_add (test_set_iter); hb_test_add (test_set_empty);