X-Git-Url: https://git.saurik.com/redis.git/blobdiff_plain/a7159fe817b163d17ff64fae0d459bbe786280ef..4264459141ee8d649dfb905a9d89adfca920728d:/tests/unit/type/set.tcl

diff --git a/tests/unit/type/set.tcl b/tests/unit/type/set.tcl
index 58ea2b5b..ec412b40 100644
--- a/tests/unit/type/set.tcl
+++ b/tests/unit/type/set.tcl
@@ -1,151 +1,379 @@
-start_server {tags {"set"}} {
-    test {SADD, SCARD, SISMEMBER, SMEMBERS basics} {
-        r sadd myset foo
-        r sadd myset bar
-        list [r scard myset] [r sismember myset foo] \
-            [r sismember myset bar] [r sismember myset bla] \
-            [lsort [r smembers myset]]
-    } {2 1 1 0 {bar foo}}
-
-    test {SADD adding the same element multiple times} {
-        r sadd myset foo
-        r sadd myset foo
-        r sadd myset foo
-        r scard myset
-    } {2}
+start_server {
+    tags {"set"}
+    overrides {
+        "set-max-intset-entries" 512
+    }
+} {
+    proc create_set {key entries} {
+        r del $key
+        foreach entry $entries { r sadd $key $entry }
+    }
+
+    test {SADD, SCARD, SISMEMBER, SMEMBERS basics - regular set} {
+        create_set myset {foo}
+        assert_encoding hashtable myset
+        assert_equal 1 [r sadd myset bar]
+        assert_equal 0 [r sadd myset bar]
+        assert_equal 2 [r scard myset]
+        assert_equal 1 [r sismember myset foo]
+        assert_equal 1 [r sismember myset bar]
+        assert_equal 0 [r sismember myset bla]
+        assert_equal {bar foo} [lsort [r smembers myset]]
+    }
+
+    test {SADD, SCARD, SISMEMBER, SMEMBERS basics - intset} {
+        create_set myset {17}
+        assert_encoding intset myset
+        assert_equal 1 [r sadd myset 16]
+        assert_equal 0 [r sadd myset 16]
+        assert_equal 2 [r scard myset]
+        assert_equal 1 [r sismember myset 16]
+        assert_equal 1 [r sismember myset 17]
+        assert_equal 0 [r sismember myset 18]
+        assert_equal {16 17} [lsort [r smembers myset]]
+    }
 
     test {SADD against non set} {
         r lpush mylist foo
-        catch {r sadd mylist bar} err
-        format $err
-    } {ERR*kind*}
+        assert_error ERR*kind* {r sadd mylist bar}
+    }
+
+    test "SADD a non-integer against an intset" {
+        create_set myset {1 2 3}
+        assert_encoding intset myset
+        assert_equal 1 [r sadd myset a]
+        assert_encoding hashtable myset
+    }
+
+    test "SADD an integer larger than 64 bits" {
+        create_set myset {213244124402402314402033402}
+        assert_encoding hashtable myset
+        assert_equal 1 [r sismember myset 213244124402402314402033402]
+    }
+
+    test "SADD overflows the maximum allowed integers in an intset" {
+        r del myset
+        for {set i 0} {$i < 512} {incr i} { r sadd myset $i }
+        assert_encoding intset myset
+        assert_equal 1 [r sadd myset 512]
+        assert_encoding hashtable myset
+    }
+
+    test {Variadic SADD} {
+        r del myset
+        assert_equal 3 [r sadd myset a b c]
+        assert_equal 2 [r sadd myset A a b c B]
+        assert_equal [lsort {A a b c B}] [lsort [r smembers myset]]
+    }
+
+    test "Set encoding after DEBUG RELOAD" {
+        r del myintset myhashset mylargeintset
+        for {set i 0} {$i <  100} {incr i} { r sadd myintset $i }
+        for {set i 0} {$i < 1280} {incr i} { r sadd mylargeintset $i }
+        for {set i 0} {$i <  256} {incr i} { r sadd myhashset [format "i%03d" $i] }
+        assert_encoding intset myintset
+        assert_encoding hashtable mylargeintset
+        assert_encoding hashtable myhashset
 
-    test {SREM basics} {
-        r sadd myset ciao
-        r srem myset foo
+        r debug reload
+        assert_encoding intset myintset
+        assert_encoding hashtable mylargeintset
+        assert_encoding hashtable myhashset
+    }
+
+    test {SREM basics - regular set} {
+        create_set myset {foo bar ciao}
+        assert_encoding hashtable myset
+        assert_equal 0 [r srem myset qux]
+        assert_equal 1 [r srem myset foo]
+        assert_equal {bar ciao} [lsort [r smembers myset]]
+    }
+
+    test {SREM basics - intset} {
+        create_set myset {3 4 5}
+        assert_encoding intset myset
+        assert_equal 0 [r srem myset 6]
+        assert_equal 1 [r srem myset 4]
+        assert_equal {3 5} [lsort [r smembers myset]]
+    }
+
+    test {SREM with multiple arguments} {
+        r del myset
+        r sadd myset a b c d
+        assert_equal 0 [r srem myset k k k]
+        assert_equal 2 [r srem myset b d x y]
         lsort [r smembers myset]
-    } {bar ciao}
+    } {a c}
 
-    test {Mass SADD and SINTER with two sets} {
-        for {set i 0} {$i < 1000} {incr i} {
+    test {SREM variadic version with more args needed to destroy the key} {
+        r del myset
+        r sadd myset 1 2 3
+        r srem myset 1 2 3 4 5 6 7 8
+    } {3}
+
+    foreach {type} {hashtable intset} {
+        for {set i 1} {$i <= 5} {incr i} {
+            r del [format "set%d" $i]
+        }
+        for {set i 0} {$i < 200} {incr i} {
             r sadd set1 $i
-            r sadd set2 [expr $i+995]
+            r sadd set2 [expr $i+195]
         }
-        lsort [r sinter set1 set2]
-    } {995 996 997 998 999}
+        foreach i {199 195 1000 2000} {
+            r sadd set3 $i
+        }
+        for {set i 5} {$i < 200} {incr i} {
+            r sadd set4 $i
+        }
+        r sadd set5 0
 
-    test {SUNION with two sets} {
-        lsort [r sunion set1 set2]
-    } [lsort -uniq "[r smembers set1] [r smembers set2]"]
+        # To make sure the sets are encoded as the type we are testing -- also
+        # when the VM is enabled and the values may be swapped in and out
+        # while the tests are running -- an extra element is added to every
+        # set that determines its encoding.
+        set large 200
+        if {$type eq "hashtable"} {
+            set large foo
+        }
 
-    test {SINTERSTORE with two sets} {
-        r sinterstore setres set1 set2
-        lsort [r smembers setres]
-    } {995 996 997 998 999}
+        for {set i 1} {$i <= 5} {incr i} {
+            r sadd [format "set%d" $i] $large
+        }
 
-    test {SINTERSTORE with two sets, after a DEBUG RELOAD} {
-        r debug reload
-        r sinterstore setres set1 set2
-        lsort [r smembers setres]
-    } {995 996 997 998 999}
+        test "Generated sets must be encoded as $type" {
+            for {set i 1} {$i <= 5} {incr i} {
+                assert_encoding $type [format "set%d" $i]
+            }
+        }
+
+        test "SINTER with two sets - $type" {
+            assert_equal [list 195 196 197 198 199 $large] [lsort [r sinter set1 set2]]
+        }
+
+        test "SINTERSTORE with two sets - $type" {
+            r sinterstore setres set1 set2
+            assert_encoding $type setres
+            assert_equal [list 195 196 197 198 199 $large] [lsort [r smembers setres]]
+        }
+
+        test "SINTERSTORE with two sets, after a DEBUG RELOAD - $type" {
+            r debug reload
+            r sinterstore setres set1 set2
+            assert_encoding $type setres
+            assert_equal [list 195 196 197 198 199 $large] [lsort [r smembers setres]]
+        }
+
+        test "SUNION with two sets - $type" {
+            set expected [lsort -uniq "[r smembers set1] [r smembers set2]"]
+            assert_equal $expected [lsort [r sunion set1 set2]]
+        }
+
+        test "SUNIONSTORE with two sets - $type" {
+            r sunionstore setres set1 set2
+            assert_encoding $type setres
+            set expected [lsort -uniq "[r smembers set1] [r smembers set2]"]
+            assert_equal $expected [lsort [r smembers setres]]
+        }
 
-    test {SUNIONSTORE with two sets} {
-        r sunionstore setres set1 set2
-        lsort [r smembers setres]
-    } [lsort -uniq "[r smembers set1] [r smembers set2]"]
+        test "SINTER against three sets - $type" {
+            assert_equal [list 195 199 $large] [lsort [r sinter set1 set2 set3]]
+        }
+
+        test "SINTERSTORE with three sets - $type" {
+            r sinterstore setres set1 set2 set3
+            assert_equal [list 195 199 $large] [lsort [r smembers setres]]
+        }
+
+        test "SUNION with non existing keys - $type" {
+            set expected [lsort -uniq "[r smembers set1] [r smembers set2]"]
+            assert_equal $expected [lsort [r sunion nokey1 set1 set2 nokey2]]
+        }
+
+        test "SDIFF with two sets - $type" {
+            assert_equal {0 1 2 3 4} [lsort [r sdiff set1 set4]]
+        }
+
+        test "SDIFF with three sets - $type" {
+            assert_equal {1 2 3 4} [lsort [r sdiff set1 set4 set5]]
+        }
 
-    test {SUNIONSTORE against non existing keys} {
+        test "SDIFFSTORE with three sets - $type" {
+            r sdiffstore setres set1 set4 set5
+            # The type is determined by type of the first key to diff against.
+            # See the implementation for more information.
+            assert_encoding $type setres
+            assert_equal {1 2 3 4} [lsort [r smembers setres]]
+        }
+    }
+
+    test "SINTER against non-set should throw error" {
+        r set key1 x
+        assert_error "ERR*wrong kind*" {r sinter key1 noset}
+    }
+
+    test "SUNION against non-set should throw error" {
+        r set key1 x
+        assert_error "ERR*wrong kind*" {r sunion key1 noset}
+    }
+
+    test "SINTER should handle non existing key as empty" {
+        r del set1 set2 set3
+        r sadd set1 a b c
+        r sadd set2 b c d
+        r sinter set1 set2 set3
+    } {}
+
+    test "SINTER with same integer elements but different encoding" {
+        r del set1 set2
+        r sadd set1 1 2 3
+        r sadd set2 1 2 3 a
+        r srem set2 a
+        assert_encoding intset set1
+        assert_encoding hashtable set2
+        lsort [r sinter set1 set2]
+    } {1 2 3}
+
+    test "SINTERSTORE against non existing keys should delete dstkey" {
         r set setres xxx
-        list [r sunionstore setres foo111 bar222] [r exists xxx]
-    } {0 0}
-
-    test {SINTER against three sets} {
-        r sadd set3 999
-        r sadd set3 995
-        r sadd set3 1000
-        r sadd set3 2000
-        lsort [r sinter set1 set2 set3]
-    } {995 999}
-
-    test {SINTERSTORE with three sets} {
-        r sinterstore setres set1 set2 set3
-        lsort [r smembers setres]
-    } {995 999}
-
-    test {SUNION with non existing keys} {
-        lsort [r sunion nokey1 set1 set2 nokey2]
-    } [lsort -uniq "[r smembers set1] [r smembers set2]"]
-
-    test {SDIFF with two sets} {
-        for {set i 5} {$i < 1000} {incr i} {
-            r sadd set4 $i
+        assert_equal 0 [r sinterstore setres foo111 bar222]
+        assert_equal 0 [r exists setres]
+    }
+
+    test "SUNIONSTORE against non existing keys should delete dstkey" {
+        r set setres xxx
+        assert_equal 0 [r sunionstore setres foo111 bar222]
+        assert_equal 0 [r exists setres]
+    }
+
+    foreach {type contents} {hashtable {a b c} intset {1 2 3}} {
+        test "SPOP basics - $type" {
+            create_set myset $contents
+            assert_encoding $type myset
+            assert_equal $contents [lsort [list [r spop myset] [r spop myset] [r spop myset]]]
+            assert_equal 0 [r scard myset]
         }
-        lsort [r sdiff set1 set4]
-    } {0 1 2 3 4}
 
-    test {SDIFF with three sets} {
-        r sadd set5 0
-        lsort [r sdiff set1 set4 set5]
-    } {1 2 3 4}
+        test "SRANDMEMBER - $type" {
+            create_set myset $contents
+            unset -nocomplain myset
+            array set myset {}
+            for {set i 0} {$i < 100} {incr i} {
+                set myset([r srandmember myset]) 1
+            }
+            assert_equal $contents [lsort [array names myset]]
+        }
+    }
 
-    test {SDIFFSTORE with three sets} {
-        r sdiffstore sres set1 set4 set5
-        lsort [r smembers sres]
-    } {1 2 3 4}
+    proc setup_move {} {
+        r del myset3 myset4
+        create_set myset1 {1 a b}
+        create_set myset2 {2 3 4}
+        assert_encoding hashtable myset1
+        assert_encoding intset myset2
+    }
 
-    test {SPOP basics} {
-        r del myset
-        r sadd myset 1
-        r sadd myset 2
-        r sadd myset 3
-        list [lsort [list [r spop myset] [r spop myset] [r spop myset]]] [r scard myset]
-    } {{1 2 3} 0}
-    
-    test {SRANDMEMBER} {
-        r del myset
-        r sadd myset a
-        r sadd myset b
-        r sadd myset c
-        unset -nocomplain myset
-        array set myset {}
-        for {set i 0} {$i < 100} {incr i} {
-            set myset([r srandmember myset]) 1
-        }
-        lsort [array names myset]
-    } {a b c}
-    
-    test {SMOVE basics} {
-        r sadd myset1 a
-        r sadd myset1 b
-        r sadd myset1 c
-        r sadd myset2 x
-        r sadd myset2 y
-        r sadd myset2 z
-        r smove myset1 myset2 a
-        list [lsort [r smembers myset2]] [lsort [r smembers myset1]]
-    } {{a x y z} {b c}}
-
-    test {SMOVE non existing key} {
-        list [r smove myset1 myset2 foo] [lsort [r smembers myset2]] [lsort [r smembers myset1]]
-    } {0 {a x y z} {b c}}
-
-    test {SMOVE non existing src set} {
-        list [r smove noset myset2 foo] [lsort [r smembers myset2]]
-    } {0 {a x y z}}
-
-    test {SMOVE non existing dst set} {
-        list [r smove myset2 myset3 y] [lsort [r smembers myset2]] [lsort [r smembers myset3]]
-    } {1 {a x z} y}
-
-    test {SMOVE wrong src key type} {
+    test "SMOVE basics - from regular set to intset" {
+        # move a non-integer element to an intset should convert encoding
+        setup_move
+        assert_equal 1 [r smove myset1 myset2 a]
+        assert_equal {1 b} [lsort [r smembers myset1]]
+        assert_equal {2 3 4 a} [lsort [r smembers myset2]]
+        assert_encoding hashtable myset2
+
+        # move an integer element should not convert the encoding
+        setup_move
+        assert_equal 1 [r smove myset1 myset2 1]
+        assert_equal {a b} [lsort [r smembers myset1]]
+        assert_equal {1 2 3 4} [lsort [r smembers myset2]]
+        assert_encoding intset myset2
+    }
+
+    test "SMOVE basics - from intset to regular set" {
+        setup_move
+        assert_equal 1 [r smove myset2 myset1 2]
+        assert_equal {1 2 a b} [lsort [r smembers myset1]]
+        assert_equal {3 4} [lsort [r smembers myset2]]
+    }
+
+    test "SMOVE non existing key" {
+        setup_move
+        assert_equal 0 [r smove myset1 myset2 foo]
+        assert_equal {1 a b} [lsort [r smembers myset1]]
+        assert_equal {2 3 4} [lsort [r smembers myset2]]
+    }
+
+    test "SMOVE non existing src set" {
+        setup_move
+        assert_equal 0 [r smove noset myset2 foo]
+        assert_equal {2 3 4} [lsort [r smembers myset2]]
+    }
+
+    test "SMOVE from regular set to non existing destination set" {
+        setup_move
+        assert_equal 1 [r smove myset1 myset3 a]
+        assert_equal {1 b} [lsort [r smembers myset1]]
+        assert_equal {a} [lsort [r smembers myset3]]
+        assert_encoding hashtable myset3
+    }
+
+    test "SMOVE from intset to non existing destination set" {
+        setup_move
+        assert_equal 1 [r smove myset2 myset3 2]
+        assert_equal {3 4} [lsort [r smembers myset2]]
+        assert_equal {2} [lsort [r smembers myset3]]
+        assert_encoding intset myset3
+    }
+
+    test "SMOVE wrong src key type" {
         r set x 10
-        catch {r smove x myset2 foo} err
-        format $err
-    } {ERR*}
+        assert_error "ERR*wrong kind*" {r smove x myset2 foo}
+    }
 
-    test {SMOVE wrong dst key type} {
+    test "SMOVE wrong dst key type" {
         r set x 10
-        catch {r smove myset2 x foo} err
-        format $err
-    } {ERR*}
+        assert_error "ERR*wrong kind*" {r smove myset2 x foo}
+    }
+
+    test "SMOVE with identical source and destination" {
+        r del set
+        r sadd set a b c
+        r smove set set b
+        lsort [r smembers set]
+    } {a b c}
+
+    tags {slow} {
+        test {intsets implementation stress testing} {
+            for {set j 0} {$j < 20} {incr j} {
+                unset -nocomplain s
+                array set s {}
+                r del s
+                set len [randomInt 1024]
+                for {set i 0} {$i < $len} {incr i} {
+                    randpath {
+                        set data [randomInt 65536]
+                    } {
+                        set data [randomInt 4294967296]
+                    } {
+                        set data [randomInt 18446744073709551616]
+                    }
+                    set s($data) {}
+                    r sadd s $data
+                }
+                assert_equal [lsort [r smembers s]] [lsort [array names s]]
+                set len [array size s]
+                for {set i 0} {$i < $len} {incr i} {
+                    set e [r spop s]
+                    if {![info exists s($e)]} {
+                        puts "Can't find '$e' on local array"
+                        puts "Local array: [lsort [r smembers s]]"
+                        puts "Remote array: [lsort [array names s]]"
+                        error "exception"
+                    }
+                    array unset s $e
+                }
+                assert_equal [r scard s] 0
+                assert_equal [array size s] 0
+            }
+        }
+    }
 }