"Fossies" - the Fresh Open Source Software Archive  

Source code changes of the file "tests/unit/geo.tcl" between
redis-6.2-rc3.tar.gz and redis-6.2.0.tar.gz

About: redis is an advanced key-value store. It is often referred to as a data structure server since keys can contain strings, hashes, lists, sets and sorted sets.

geo.tcl  (redis-6.2-rc3):geo.tcl  (redis-6.2.0)
# Helper functions to simulate search-in-radius in the Tcl side in order to # Helper functions to simulate search-in-radius in the Tcl side in order to
# verify the Redis implementation with a fuzzy test. # verify the Redis implementation with a fuzzy test.
proc geo_degrad deg {expr {$deg*atan(1)*8/360}} proc geo_degrad deg {expr {$deg*(atan(1)*8/360)}}
proc geo_raddeg rad {expr {$rad/(atan(1)*8/360)}}
proc geo_distance {lon1d lat1d lon2d lat2d} { proc geo_distance {lon1d lat1d lon2d lat2d} {
set lon1r [geo_degrad $lon1d] set lon1r [geo_degrad $lon1d]
set lat1r [geo_degrad $lat1d] set lat1r [geo_degrad $lat1d]
set lon2r [geo_degrad $lon2d] set lon2r [geo_degrad $lon2d]
set lat2r [geo_degrad $lat2d] set lat2r [geo_degrad $lat2d]
set v [expr {sin(($lon2r - $lon1r) / 2)}] set v [expr {sin(($lon2r - $lon1r) / 2)}]
set u [expr {sin(($lat2r - $lat1r) / 2)}] set u [expr {sin(($lat2r - $lat1r) / 2)}]
expr {2.0 * 6372797.560856 * \ expr {2.0 * 6372797.560856 * \
asin(sqrt($u * $u + cos($lat1r) * cos($lat2r) * $v * $v))} asin(sqrt($u * $u + cos($lat1r) * cos($lat2r) * $v * $v))}
skipping to change at line 45 skipping to change at line 46
foreach Item $List2 { foreach Item $List2 {
if {[lsearch -exact $List1 $Item] == -1} { if {[lsearch -exact $List1 $Item] == -1} {
if {[lsearch -exact $DiffList $Item] == -1} { if {[lsearch -exact $DiffList $Item] == -1} {
lappend DiffList $Item lappend DiffList $Item
} }
} }
} }
return $DiffList return $DiffList
} }
# return true If a point in circle.
# search_lon and search_lat define the center of the circle,
# and lon, lat define the point being searched.
proc pointInCircle {radius_km lon lat search_lon search_lat} {
set radius_m [expr {$radius_km*1000}]
set distance [geo_distance $lon $lat $search_lon $search_lat]
if {$distance < $radius_m} {
return true
}
return false
}
# return true If a point in rectangle.
# search_lon and search_lat define the center of the rectangle,
# and lon, lat define the point being searched.
# error: can adjust the width and height of the rectangle according to the error
proc pointInRectangle {width_km height_km lon lat search_lon search_lat error} {
set width_m [expr {$width_km*1000*$error/2}]
set height_m [expr {$height_km*1000*$error/2}]
set lon_distance [geo_distance $lon $lat $search_lon $lat]
set lat_distance [geo_distance $lon $lat $lon $search_lat]
if {$lon_distance > $width_m || $lat_distance > $height_m} {
return false
}
return true
}
# The following list represents sets of random seed, search position # The following list represents sets of random seed, search position
# and radius that caused bugs in the past. It is used by the randomized # and radius that caused bugs in the past. It is used by the randomized
# test later as a starting point. When the regression vectors are scanned # test later as a starting point. When the regression vectors are scanned
# the code reverts to using random data. # the code reverts to using random data.
# #
# The format is: seed km lon lat # The format is: seed km lon lat
set regression_vectors { set regression_vectors {
{1482225976969 7083 81.634948934258375 30.561509253718668} {1482225976969 7083 81.634948934258375 30.561509253718668}
{1482340074151 5416 -70.863281847379767 -46.347003465679947} {1482340074151 5416 -70.863281847379767 -46.347003465679947}
{1499014685896 6064 -89.818768962202014 -40.463868561416803} {1499014685896 6064 -89.818768962202014 -40.463868561416803}
skipping to change at line 228 skipping to change at line 257
r geoadd Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catan ia" r geoadd Sicily 13.361389 38.115556 "Palermo" 15.087269 37.502669 "Catan ia"
r geoadd Sicily 12.758489 38.788135 "edge1" 17.241510 38.788135 "eage2 " r geoadd Sicily 12.758489 38.788135 "edge1" 17.241510 38.788135 "eage2 "
set ret1 [r georadius Sicily 15 37 200 km asc] set ret1 [r georadius Sicily 15 37 200 km asc]
assert_equal $ret1 {Catania Palermo} assert_equal $ret1 {Catania Palermo}
set ret2 [r geosearch Sicily fromlonlat 15 37 bybox 400 400 km asc] set ret2 [r geosearch Sicily fromlonlat 15 37 bybox 400 400 km asc]
assert_equal $ret2 {Catania Palermo eage2 edge1} assert_equal $ret2 {Catania Palermo eage2 edge1}
} }
test {GEOSEARCH non square, long and narrow} { test {GEOSEARCH non square, long and narrow} {
r del Sicily r del Sicily
r geoadd Sicily 12.75 37.00 "test1" r geoadd Sicily 12.75 36.995 "test1"
r geoadd Sicily 12.75 36.50 "test2" r geoadd Sicily 12.75 36.50 "test2"
r geoadd Sicily 13.00 36.50 "test3" r geoadd Sicily 13.00 36.50 "test3"
# box height=2km width=400km # box height=2km width=400km
set ret1 [r geosearch Sicily fromlonlat 15 37 bybox 2 400 km] set ret1 [r geosearch Sicily fromlonlat 15 37 bybox 400 2 km]
assert_equal $ret1 {test1} assert_equal $ret1 {test1}
# Add a western Hemisphere point # Add a western Hemisphere point
r geoadd Sicily -1 37.00 "test3" r geoadd Sicily -1 37.00 "test3"
set ret2 [r geosearch Sicily fromlonlat 15 37 bybox 2 3000 km asc] set ret2 [r geosearch Sicily fromlonlat 15 37 bybox 3000 2 km asc]
assert_equal $ret2 {test1 test3} assert_equal $ret2 {test1 test3}
} }
test {GEOSEARCH corner point test} {
r del Sicily
r geoadd Sicily 12.758489 38.788135 edge1 17.241510 38.788135 edge2 17.2
50000 35.202000 edge3 12.750000 35.202000 edge4 12.748489955781654 37 edge5 15 3
8.798135872540925 edge6 17.251510044218346 37 edge7 15 35.201864127459075 edge8
12.692799634687903 38.798135872540925 corner1 12.692799634687903 38.798135872540
925 corner2 17.200560937451133 35.201864127459075 corner3 12.799439062548865 35.
201864127459075 corner4
set ret [lsort [r geosearch Sicily fromlonlat 15 37 bybox 400 400 km asc
]]
assert_equal $ret {edge1 edge2 edge5 edge7}
}
test {GEORADIUSBYMEMBER withdist (sorted)} { test {GEORADIUSBYMEMBER withdist (sorted)} {
r georadiusbymember nyc "wtc one" 7 km withdist r georadiusbymember nyc "wtc one" 7 km withdist
} {{{wtc one} 0.0000} {{union square} 3.2544} {{central park n/q/r} 6.7000} {4545 6.1975} {{lic market} 6.8969}} } {{{wtc one} 0.0000} {{union square} 3.2544} {{central park n/q/r} 6.7000} {4545 6.1975} {{lic market} 6.8969}}
test {GEOHASH is able to return geohash strings} { test {GEOHASH is able to return geohash strings} {
# Example from Wikipedia. # Example from Wikipedia.
r del points r del points
r geoadd points -5.6 42.6 test r geoadd points -5.6 42.6 test
lindex [r geohash points test] 0 lindex [r geohash points test] 0
} {ezs42e44yx0} } {ezs42e44yx0}
skipping to change at line 363 skipping to change at line 399
assert {[r zcard points2] == 1} assert {[r zcard points2] == 1}
set res [r zrange points2 0 -1 withscores] set res [r zrange points2 0 -1 withscores]
assert {[lindex $res 0] eq "Palermo"} assert {[lindex $res 0] eq "Palermo"}
r georadius points 13.361389 38.115556 500 km storedist points2 desc cou nt 1 r georadius points 13.361389 38.115556 500 km storedist points2 desc cou nt 1
assert {[r zcard points2] == 1} assert {[r zcard points2] == 1}
set res [r zrange points2 0 -1 withscores] set res [r zrange points2 0 -1 withscores]
assert {[lindex $res 0] eq "Catania"} assert {[lindex $res 0] eq "Catania"}
} }
test {GEOADD + GEORANGE randomized test} { test {GEOSEARCH the box spans -180° or 180°} {
set attempt 30 r del points
r geoadd points 179.5 36 point1
r geoadd points -179.5 36 point2
assert_equal {point1 point2} [r geosearch points fromlonlat 179 37 bybox
400 400 km asc]
assert_equal {point2 point1} [r geosearch points fromlonlat -179 37 bybo
x 400 400 km asc]
}
foreach {type} {byradius bybox} {
test "GEOSEARCH fuzzy test - $type" {
if {$::accurate} { set attempt 300 } else { set attempt 30 }
while {[incr attempt -1]} { while {[incr attempt -1]} {
set rv [lindex $regression_vectors $rv_idx] set rv [lindex $regression_vectors $rv_idx]
incr rv_idx incr rv_idx
set radius_km 0; set width_km 0; set height_km 0
unset -nocomplain debuginfo unset -nocomplain debuginfo
set srand_seed [clock milliseconds] set srand_seed [clock milliseconds]
if {$rv ne {}} {set srand_seed [lindex $rv 0]} if {$rv ne {}} {set srand_seed [lindex $rv 0]}
lappend debuginfo "srand_seed is $srand_seed" lappend debuginfo "srand_seed is $srand_seed"
expr {srand($srand_seed)} ; # If you need a reproducible run expr {srand($srand_seed)} ; # If you need a reproducible run
r del mypoints r del mypoints
if {[randomInt 10] == 0} { if {[randomInt 10] == 0} {
# From time to time use very big radiuses # From time to time use very big radiuses
set radius_km [expr {[randomInt 50000]+10}] if {$type == "byradius"} {
set radius_km [expr {[randomInt 5000]+10}]
} elseif {$type == "bybox"} {
set width_km [expr {[randomInt 5000]+10}]
set height_km [expr {[randomInt 5000]+10}]
}
} else { } else {
# Normally use a few - ~200km radiuses to stress # Normally use a few - ~200km radiuses to stress
# test the code the most in edge cases. # test the code the most in edge cases.
set radius_km [expr {[randomInt 200]+10}] if {$type == "byradius"} {
set radius_km [expr {[randomInt 200]+10}]
} elseif {$type == "bybox"} {
set width_km [expr {[randomInt 200]+10}]
set height_km [expr {[randomInt 200]+10}]
}
}
if {$rv ne {}} {
set radius_km [lindex $rv 1]
set width_km [lindex $rv 1]
set height_km [lindex $rv 1]
} }
if {$rv ne {}} {set radius_km [lindex $rv 1]}
set radius_m [expr {$radius_km*1000}]
geo_random_point search_lon search_lat geo_random_point search_lon search_lat
if {$rv ne {}} { if {$rv ne {}} {
set search_lon [lindex $rv 2] set search_lon [lindex $rv 2]
set search_lat [lindex $rv 3] set search_lat [lindex $rv 3]
} }
lappend debuginfo "Search area: $search_lon,$search_lat $radius_km k m" lappend debuginfo "Search area: $search_lon,$search_lat $radius_km $ width_km $height_km km"
set tcl_result {} set tcl_result {}
set argv {} set argv {}
for {set j 0} {$j < 20000} {incr j} { for {set j 0} {$j < 20000} {incr j} {
geo_random_point lon lat geo_random_point lon lat
lappend argv $lon $lat "place:$j" lappend argv $lon $lat "place:$j"
set distance [geo_distance $lon $lat $search_lon $search_lat] if {$type == "byradius"} {
if {$distance < $radius_m} { if {[pointInCircle $radius_km $lon $lat $search_lon $search_
lappend tcl_result "place:$j" lat]} {
lappend tcl_result "place:$j"
}
} elseif {$type == "bybox"} {
if {[pointInRectangle $width_km $height_km $lon $lat $search
_lon $search_lat 1]} {
lappend tcl_result "place:$j"
}
} }
lappend debuginfo "place:$j $lon $lat [expr {$distance/1000}] km " lappend debuginfo "place:$j $lon $lat"
} }
r geoadd mypoints {*}$argv r geoadd mypoints {*}$argv
set res [lsort [r georadius mypoints $search_lon $search_lat $radius if {$type == "byradius"} {
_km km]] set res [lsort [r geosearch mypoints fromlonlat $search_lon $sea
rch_lat byradius $radius_km km]]
} elseif {$type == "bybox"} {
set res [lsort [r geosearch mypoints fromlonlat $search_lon $sea
rch_lat bybox $width_km $height_km km]]
}
set res2 [lsort $tcl_result] set res2 [lsort $tcl_result]
set test_result OK set test_result OK
if {$res != $res2} { if {$res != $res2} {
set rounding_errors 0 set rounding_errors 0
set diff [compare_lists $res $res2] set diff [compare_lists $res $res2]
foreach place $diff { foreach place $diff {
lassign [lindex [r geopos mypoints $place] 0] lon lat
set mydist [geo_distance $lon $lat $search_lon $search_lat] set mydist [geo_distance $lon $lat $search_lon $search_lat]
set mydist [expr $mydist/1000] set mydist [expr $mydist/1000]
if {($mydist / $radius_km) > 0.999} { if {$type == "byradius"} {
incr rounding_errors if {($mydist / $radius_km) > 0.999} {
continue incr rounding_errors
} continue
if {$mydist < $radius_m} { }
# This is a false positive for redis since given the if {$mydist < [expr {$radius_km*1000}]} {
# same points the higher precision calculation provided # This is a false positive for redis since given the
# by TCL shows the point within range # same points the higher precision calculation provi
incr rounding_errors ded
continue # by TCL shows the point within range
incr rounding_errors
continue
}
} elseif {$type == "bybox"} {
# we add 0.1% error for floating point calculation error
if {[pointInRectangle $width_km $height_km $lon $lat $se
arch_lon $search_lat 1.001]} {
incr rounding_errors
continue
}
} }
} }
# Make sure this is a real error and not a rounidng issue. # Make sure this is a real error and not a rounidng issue.
if {[llength $diff] == $rounding_errors} { if {[llength $diff] == $rounding_errors} {
set res $res2; # Error silenced set res $res2; # Error silenced
} }
} }
if {$res != $res2} { if {$res != $res2} {
skipping to change at line 450 skipping to change at line 527
foreach place $diff { foreach place $diff {
if {[lsearch -exact $res2 $place] != -1} { if {[lsearch -exact $res2 $place] != -1} {
set where "(only in Tcl)" set where "(only in Tcl)"
} else { } else {
set where "(only in Redis)" set where "(only in Redis)"
} }
lassign [lindex [r geopos mypoints $place] 0] lon lat lassign [lindex [r geopos mypoints $place] 0] lon lat
set mydist [geo_distance $lon $lat $search_lon $search_lat] set mydist [geo_distance $lon $lat $search_lon $search_lat]
set mydist [expr $mydist/1000] set mydist [expr $mydist/1000]
puts "$place -> [r geopos mypoints $place] $mydist $where" puts "$place -> [r geopos mypoints $place] $mydist $where"
if {($mydist / $radius_km) > 0.999} {incr rounding_errors}
} }
set test_result FAIL set test_result FAIL
} }
unset -nocomplain debuginfo unset -nocomplain debuginfo
if {$test_result ne {OK}} break if {$test_result ne {OK}} break
} }
set test_result set test_result
} {OK} } {OK}
}
test {GEOSEARCH box edges fuzzy test} {
if {$::accurate} { set attempt 300 } else { set attempt 30 }
while {[incr attempt -1]} {
unset -nocomplain debuginfo
set srand_seed [clock milliseconds]
lappend debuginfo "srand_seed is $srand_seed"
expr {srand($srand_seed)} ; # If you need a reproducible run
r del mypoints
geo_random_point search_lon search_lat
set width_m [expr {[randomInt 10000]+10}]
set height_m [expr {[randomInt 10000]+10}]
set lat_delta [geo_raddeg [expr {$height_m/2/6372797.560856}]]
set long_delta_top [geo_raddeg [expr {$width_m/2/6372797.560856/cos(
[geo_degrad [expr {$search_lat+$lat_delta}]])}]]
set long_delta_middle [geo_raddeg [expr {$width_m/2/6372797.560856/c
os([geo_degrad $search_lat])}]]
set long_delta_bottom [geo_raddeg [expr {$width_m/2/6372797.560856/c
os([geo_degrad [expr {$search_lat-$lat_delta}]])}]]
# Total of 8 points are generated, which are located at each vertex
and the center of each side
set points(north) [list $search_lon [expr {$search_lat+$lat_delta}]]
set points(south) [list $search_lon [expr {$search_lat-$lat_delta}]]
set points(east) [list [expr {$search_lon+$long_delta_middle}] $sear
ch_lat]
set points(west) [list [expr {$search_lon-$long_delta_middle}] $sear
ch_lat]
set points(north_east) [list [expr {$search_lon+$long_delta_top}] [e
xpr {$search_lat+$lat_delta}]]
set points(north_west) [list [expr {$search_lon-$long_delta_top}] [e
xpr {$search_lat+$lat_delta}]]
set points(south_east) [list [expr {$search_lon+$long_delta_bottom}]
[expr {$search_lat-$lat_delta}]]
set points(south_west) [list [expr {$search_lon-$long_delta_bottom}]
[expr {$search_lat-$lat_delta}]]
lappend debuginfo "Search area: geosearch mypoints fromlonlat $searc
h_lon $search_lat bybox $width_m $height_m m"
set tcl_result {}
foreach name [array names points] {
set x [lindex $points($name) 0]
set y [lindex $points($name) 1]
# If longitude crosses -180° or 180°, we need to convert it.
# latitude doesn't have this problem, because it's scope is -70~
70, see geo_random_point
if {$x > 180} {
set x [expr {$x-360}]
} elseif {$x < -180} {
set x [expr {$x+360}]
}
r geoadd mypoints $x $y place:$name
lappend tcl_result "place:$name"
lappend debuginfo "geoadd mypoints $x $y place:$name"
}
set res2 [lsort $tcl_result]
# make the box larger by two meter in each direction to put the coor
dinate slightly inside the box.
set height_new [expr {$height_m+4}]
set width_new [expr {$width_m+4}]
set res [lsort [r geosearch mypoints fromlonlat $search_lon $search_
lat bybox $width_new $height_new m]]
if {$res != $res2} {
set diff [compare_lists $res $res2]
lappend debuginfo "res: $res, res2: $res2, diff: $diff"
fail "place should be found, debuginfo: $debuginfo, height_new:
$height_new width_new: $width_new"
}
# The width decreases and the height increases. Only north and south
are found
set width_new [expr {$width_m-4}]
set height_new [expr {$height_m+4}]
set res [lsort [r geosearch mypoints fromlonlat $search_lon $search_
lat bybox $width_new $height_new m]]
if {$res != {place:north place:south}} {
lappend debuginfo "res: $res"
fail "place should not be found, debuginfo: $debuginfo, height_n
ew: $height_new width_new: $width_new"
}
# The width increases and the height decreases. Only ease and west a
re found
set width_new [expr {$width_m+4}]
set height_new [expr {$height_m-4}]
set res [lsort [r geosearch mypoints fromlonlat $search_lon $search_
lat bybox $width_new $height_new m]]
if {$res != {place:east place:west}} {
lappend debuginfo "res: $res"
fail "place should not be found, debuginfo: $debuginfo, height_n
ew: $height_new width_new: $width_new"
}
# make the box smaller by two meter in each direction to put the coo
rdinate slightly outside the box.
set height_new [expr {$height_m-4}]
set width_new [expr {$width_m-4}]
set res [r geosearch mypoints fromlonlat $search_lon $search_lat byb
ox $width_new $height_new m]
if {$res != ""} {
lappend debuginfo "res: $res"
fail "place should not be found, debuginfo: $debuginfo, height_n
ew: $height_new width_new: $width_new"
}
unset -nocomplain debuginfo
}
}
} }
 End of changes. 19 change blocks. 
28 lines changed or deleted 228 lines changed or added

Home  |  About  |  Features  |  All  |  Newest  |  Dox  |  Diffs  |  RSS Feeds  |  Screenshots  |  Comments  |  Imprint  |  Privacy  |  HTTP(S)