code.grnet.gr Git - ganeti-local/blob - test/ganeti.utils.algo_unittest.py

   1 #!/usr/bin/python
   2 #
   3
   4 # Copyright (C) 2011 Google Inc.
   5 #
   6 # This program is free software; you can redistribute it and/or modify
   7 # it under the terms of the GNU General Public License as published by
   8 # the Free Software Foundation; either version 2 of the License, or
   9 # (at your option) any later version.
  10 #
  11 # This program is distributed in the hope that it will be useful, but
  12 # WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 # General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with this program; if not, write to the Free Software
  18 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19 # 02110-1301, USA.
  20
  21
  22 """Script for testing ganeti.utils.algo"""
  23
  24 import unittest
  25 import random
  26 import operator
  27
  28 from ganeti import constants
  29 from ganeti import compat
  30 from ganeti.utils import algo
  31
  32 import testutils
  33
  34
  35 class TestUniqueSequence(unittest.TestCase):
  36   """Test case for UniqueSequence"""
  37
  38   def _test(self, input, expected):
  39     self.assertEqual(algo.UniqueSequence(input), expected)
  40
  41   def runTest(self):
  42     # Ordered input
  43     self._test([1, 2, 3], [1, 2, 3])
  44     self._test([1, 1, 2, 2, 3, 3], [1, 2, 3])
  45     self._test([1, 2, 2, 3], [1, 2, 3])
  46     self._test([1, 2, 3, 3], [1, 2, 3])
  47
  48     # Unordered input
  49     self._test([1, 2, 3, 1, 2, 3], [1, 2, 3])
  50     self._test([1, 1, 2, 3, 3, 1, 2], [1, 2, 3])
  51
  52     # Strings
  53     self._test(["a", "a"], ["a"])
  54     self._test(["a", "b"], ["a", "b"])
  55     self._test(["a", "b", "a"], ["a", "b"])
  56
  57
  58 class TestFindDuplicates(unittest.TestCase):
  59   """Test case for FindDuplicates"""
  60
  61   def _Test(self, seq, expected):
  62     result = algo.FindDuplicates(seq)
  63     self.assertEqual(result, algo.UniqueSequence(result))
  64     self.assertEqual(set(result), set(expected))
  65
  66   def test(self):
  67     self._Test([], [])
  68     self._Test([1, 2, 3], [])
  69     self._Test([9, 8, 8, 0, 5, 1, 7, 0, 6, 7], [8, 0, 7])
  70     for exp in [[1, 2, 3], [3, 2, 1]]:
  71       self._Test([1, 1, 2, 2, 3, 3], exp)
  72
  73     self._Test(["A", "a", "B"], [])
  74     self._Test(["a", "A", "a", "B"], ["a"])
  75     self._Test("Hello World out there!", ["e", " ", "o", "r", "t", "l"])
  76
  77     self._Test(self._Gen(False), [])
  78     self._Test(self._Gen(True), range(1, 10))
  79
  80   @staticmethod
  81   def _Gen(dup):
  82     for i in range(10):
  83       yield i
  84       if dup:
  85         for _ in range(i):
  86           yield i
  87
  88
  89 class TestNiceSort(unittest.TestCase):
  90   def test(self):
  91     self.assertEqual(algo.NiceSort([]), [])
  92     self.assertEqual(algo.NiceSort(["foo"]), ["foo"])
  93     self.assertEqual(algo.NiceSort(["bar", ""]), ["", "bar"])
  94     self.assertEqual(algo.NiceSort([",", "."]), [",", "."])
  95     self.assertEqual(algo.NiceSort(["0.1", "0.2"]), ["0.1", "0.2"])
  96     self.assertEqual(algo.NiceSort(["0;099", "0,099", "0.1", "0.2"]),
  97                      ["0,099", "0.1", "0.2", "0;099"])
  98
  99     data = ["a0", "a1", "a99", "a20", "a2", "b10", "b70", "b00", "0000"]
 100     self.assertEqual(algo.NiceSort(data),
 101                      ["0000", "a0", "a1", "a2", "a20", "a99",
 102                       "b00", "b10", "b70"])
 103
 104     data = ["a0-0", "a1-0", "a99-10", "a20-3", "a0-4", "a99-3", "a09-2",
 105             "Z", "a9-1", "A", "b"]
 106     self.assertEqual(algo.NiceSort(data),
 107                      ["A", "Z", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 108                       "a20-3", "a99-3", "a99-10", "b"])
 109     self.assertEqual(algo.NiceSort(data, key=str.lower),
 110                      ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 111                       "a20-3", "a99-3", "a99-10", "b", "Z"])
 112     self.assertEqual(algo.NiceSort(data, key=str.upper),
 113                      ["A", "a0-0", "a0-4", "a1-0", "a9-1", "a09-2",
 114                       "a20-3", "a99-3", "a99-10", "b", "Z"])
 115
 116   def testLargeA(self):
 117     data = [
 118       "Eegah9ei", "xij88brTulHYAv8IEOyU", "3jTwJPtrXOY22bwL2YoW",
 119       "Z8Ljf1Pf5eBfNg171wJR", "WvNJd91OoXvLzdEiEXa6", "uHXAyYYftCSG1o7qcCqe",
 120       "xpIUJeVT1Rp", "KOt7vn1dWXi", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
 121       "cPRi0lM7HLnSuWA2G9", "KVQqLPDjcPjf8T3oyzjcOsfkb",
 122       "guKJkXnkULealVC8CyF1xefym", "pqF8dkU5B1cMnyZuREaSOADYx",
 123       ]
 124     self.assertEqual(algo.NiceSort(data), [
 125       "3jTwJPtrXOY22bwL2YoW", "Eegah9ei", "KOt7vn1dWXi",
 126       "KVQqLPDjcPjf8T3oyzjcOsfkb", "WvNJd91OoXvLzdEiEXa6",
 127       "Z8Ljf1Pf5eBfNg171wJR", "a07h8feON165N67PIE", "bH4Q7aCu3PUPjK3JtH",
 128       "cPRi0lM7HLnSuWA2G9", "guKJkXnkULealVC8CyF1xefym",
 129       "pqF8dkU5B1cMnyZuREaSOADYx", "uHXAyYYftCSG1o7qcCqe",
 130       "xij88brTulHYAv8IEOyU", "xpIUJeVT1Rp"
 131       ])
 132
 133   def testLargeB(self):
 134     data = [
 135       "inst-0.0.0.0-0.0.0.0",
 136       "inst-0.1.0.0-0.0.0.0",
 137       "inst-0.2.0.0-0.0.0.0",
 138       "inst-0.2.1.0-0.0.0.0",
 139       "inst-0.2.2.0-0.0.0.0",
 140       "inst-0.2.2.0-0.0.0.9",
 141       "inst-0.2.2.0-0.0.3.9",
 142       "inst-0.2.2.0-0.2.0.9",
 143       "inst-0.2.2.0-0.9.0.9",
 144       "inst-0.20.2.0-0.0.0.0",
 145       "inst-0.20.2.0-0.9.0.9",
 146       "inst-10.020.2.0-0.9.0.10",
 147       "inst-15.020.2.0-0.9.1.00",
 148       "inst-100.020.2.0-0.9.0.9",
 149
 150       # Only the last group, not converted to a number anymore, differs
 151       "inst-100.020.2.0a999",
 152       "inst-100.020.2.0b000",
 153       "inst-100.020.2.0c10",
 154       "inst-100.020.2.0c101",
 155       "inst-100.020.2.0c2",
 156       "inst-100.020.2.0c20",
 157       "inst-100.020.2.0c3",
 158       "inst-100.020.2.0c39123",
 159       ]
 160
 161     rnd = random.Random(16205)
 162     for _ in range(10):
 163       testdata = data[:]
 164       rnd.shuffle(testdata)
 165       assert testdata != data
 166       self.assertEqual(algo.NiceSort(testdata), data)
 167
 168   class _CallCount:
 169     def __init__(self, fn):
 170       self.count = 0
 171       self.fn = fn
 172
 173     def __call__(self, *args):
 174       self.count += 1
 175       return self.fn(*args)
 176
 177   def testKeyfuncA(self):
 178     # Generate some random numbers
 179     rnd = random.Random(21131)
 180     numbers = [rnd.randint(0, 10000) for _ in range(999)]
 181     assert numbers != sorted(numbers)
 182
 183     # Convert to hex
 184     data = [hex(i) for i in numbers]
 185     datacopy = data[:]
 186
 187     keyfn = self._CallCount(lambda value: str(int(value, 16)))
 188
 189     # Sort with key function converting hex to decimal
 190     result = algo.NiceSort(data, key=keyfn)
 191
 192     self.assertEqual([hex(i) for i in sorted(numbers)], result)
 193     self.assertEqual(data, datacopy, msg="Input data was modified in NiceSort")
 194     self.assertEqual(keyfn.count, len(numbers),
 195                      msg="Key function was not called once per value")
 196
 197   class _TestData:
 198     def __init__(self, name, value):
 199       self.name = name
 200       self.value = value
 201
 202   def testKeyfuncB(self):
 203     rnd = random.Random(27396)
 204     data = []
 205     for i in range(123):
 206       v1 = rnd.randint(0, 5)
 207       v2 = rnd.randint(0, 5)
 208       data.append(self._TestData("inst-%s-%s-%s" % (v1, v2, i),
 209                                  (v1, v2, i)))
 210     rnd.shuffle(data)
 211     assert data != sorted(data, key=operator.attrgetter("name"))
 212
 213     keyfn = self._CallCount(operator.attrgetter("name"))
 214
 215     # Sort by name
 216     result = algo.NiceSort(data, key=keyfn)
 217
 218     self.assertEqual(result, sorted(data, key=operator.attrgetter("value")))
 219     self.assertEqual(keyfn.count, len(data),
 220                      msg="Key function was not called once per value")
 221
 222   def testNiceSortKey(self):
 223     self.assertEqual(algo.NiceSortKey(""),
 224                      ([None] * algo._SORTER_GROUPS) + [""])
 225     self.assertEqual(algo.NiceSortKey("Hello World"),
 226                      ["Hello World"] +
 227                      ([None] * int(algo._SORTER_GROUPS - 1)) + [""])
 228     self.assertEqual(algo.NiceSortKey("node1.net75.bld3.example.com"),
 229                      ["node", 1, ".net", 75, ".bld", 3, ".example.com",
 230                       None, ""])
 231
 232
 233 class TestInvertDict(unittest.TestCase):
 234   def testInvertDict(self):
 235     test_dict = { "foo": 1, "bar": 2, "baz": 5 }
 236     self.assertEqual(algo.InvertDict(test_dict),
 237                      { 1: "foo", 2: "bar", 5: "baz"})
 238
 239
 240 class TestInsertAtPos(unittest.TestCase):
 241   def test(self):
 242     a = [1, 5, 6]
 243     b = [2, 3, 4]
 244     self.assertEqual(algo.InsertAtPos(a, 1, b), [1, 2, 3, 4, 5, 6])
 245     self.assertEqual(algo.InsertAtPos(a, 0, b), b + a)
 246     self.assertEqual(algo.InsertAtPos(a, len(a), b), a + b)
 247     self.assertEqual(algo.InsertAtPos(a, 2, b), [1, 5, 2, 3, 4, 6])
 248
 249
 250 class TimeMock:
 251   def __init__(self, values):
 252     self.values = values
 253
 254   def __call__(self):
 255     return self.values.pop(0)
 256
 257
 258 class TestRunningTimeout(unittest.TestCase):
 259   def setUp(self):
 260     self.time_fn = TimeMock([0.0, 0.3, 4.6, 6.5])
 261
 262   def testRemainingFloat(self):
 263     timeout = algo.RunningTimeout(5.0, True, _time_fn=self.time_fn)
 264     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 265     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 266     self.assertAlmostEqual(timeout.Remaining(), -1.5)
 267
 268   def testRemaining(self):
 269     self.time_fn = TimeMock([0, 2, 4, 5, 6])
 270     timeout = algo.RunningTimeout(5, True, _time_fn=self.time_fn)
 271     self.assertEqual(timeout.Remaining(), 3)
 272     self.assertEqual(timeout.Remaining(), 1)
 273     self.assertEqual(timeout.Remaining(), 0)
 274     self.assertEqual(timeout.Remaining(), -1)
 275
 276   def testRemainingNonNegative(self):
 277     timeout = algo.RunningTimeout(5.0, False, _time_fn=self.time_fn)
 278     self.assertAlmostEqual(timeout.Remaining(), 4.7)
 279     self.assertAlmostEqual(timeout.Remaining(), 0.4)
 280     self.assertEqual(timeout.Remaining(), 0.0)
 281
 282   def testNegativeTimeout(self):
 283     self.assertRaises(ValueError, algo.RunningTimeout, -1.0, True)
 284
 285
 286 class TestJoinDisjointDicts(unittest.TestCase):
 287   def setUp(self):
 288     self.non_empty_dict = {"a": 1, "b": 2}
 289     self.empty_dict = dict()
 290
 291   def testWithEmptyDicts(self):
 292     self.assertEqual(self.empty_dict, algo.JoinDisjointDicts(self.empty_dict,
 293       self.empty_dict))
 294     self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
 295       self.empty_dict, self.non_empty_dict))
 296     self.assertEqual(self.non_empty_dict, algo.JoinDisjointDicts(
 297       self.non_empty_dict, self.empty_dict))
 298
 299   def testNonDisjoint(self):
 300     self.assertRaises(AssertionError, algo.JoinDisjointDicts,
 301       self.non_empty_dict, self.non_empty_dict)
 302
 303   def testCommonCase(self):
 304     dict_a = {"TEST1": 1, "TEST2": 2}
 305     dict_b = {"TEST3": 3, "TEST4": 4}
 306
 307     result = dict_a.copy()
 308     result.update(dict_b)
 309
 310     self.assertEqual(result, algo.JoinDisjointDicts(dict_a, dict_b))
 311     self.assertEqual(result, algo.JoinDisjointDicts(dict_b, dict_a))
 312
 313
 314 class TestSequenceToDict(unittest.TestCase):
 315   def testEmpty(self):
 316     self.assertEqual(algo.SequenceToDict([]), {})
 317     self.assertEqual(algo.SequenceToDict({}), {})
 318
 319   def testSimple(self):
 320     data = [(i, str(i), "test%s" % i) for i in range(391)]
 321     self.assertEqual(algo.SequenceToDict(data),
 322       dict((i, (i, str(i), "test%s" % i))
 323            for i in range(391)))
 324
 325   def testCustomKey(self):
 326     data = [(i, hex(i), "test%s" % i) for i in range(100)]
 327     self.assertEqual(algo.SequenceToDict(data, key=compat.snd),
 328       dict((hex(i), (i, hex(i), "test%s" % i))
 329            for i in range(100)))
 330     self.assertEqual(algo.SequenceToDict(data,
 331                                          key=lambda (a, b, val): hash(val)),
 332       dict((hash("test%s" % i), (i, hex(i), "test%s" % i))
 333            for i in range(100)))
 334
 335   def testDuplicate(self):
 336     self.assertRaises(ValueError, algo.SequenceToDict,
 337                       [(0, 0), (0, 0)])
 338     self.assertRaises(ValueError, algo.SequenceToDict,
 339                       [(i, ) for i in range(200)] + [(10, )])
 340
 341
 342 class TestFlatToDict(unittest.TestCase):
 343   def testNormal(self):
 344     data = [
 345       ("lv/xenvg", {"foo": "bar", "bar": "baz"}),
 346       ("lv/xenfoo", {"foo": "bar", "baz": "blubb"}),
 347       ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
 348       ("san/blubb/blibb", 54),
 349       ]
 350     reference = {
 351       "lv": {
 352         "xenvg": {"foo": "bar", "bar": "baz"},
 353         "xenfoo": {"foo": "bar", "baz": "blubb"},
 354         },
 355       "san": {
 356         "foo": {"ip": "127.0.0.1", "port": 1337},
 357         "blubb": {"blibb": 54},
 358         },
 359       }
 360     self.assertEqual(algo.FlatToDict(data), reference)
 361
 362   def testUnlikeDepth(self):
 363     data = [
 364       ("san/foo", {"ip": "127.0.0.1", "port": 1337}),
 365       ("san/foo/blubb", 23), # Another foo entry under san
 366       ("san/blubb/blibb", 54),
 367       ]
 368     self.assertRaises(AssertionError, algo.FlatToDict, data)
 369
 370
 371 if __name__ == "__main__":
 372   testutils.GanetiTestProgram()