src/native_client/src/trusted/validator_ragel/trie_test.py

   1 #!/usr/bin/python
   2 # Copyright (c) 2014 The Native Client Authors. All rights reserved.
   3 # Use of this source code is governed by a BSD-style license that can be
   4 # found in the LICENSE file.
   5
   6 import unittest
   7
   8 import trie
   9
  10
  11 class TrieTest(unittest.TestCase):
  12
  13   def MakeUncompressedTrie(self):
  14     uncompressed = trie.Node()
  15     accept = trie.AcceptInfo(input_rr='%eax', output_rr='%edx')
  16     trie.AddToUncompressedTrie(uncompressed, ['0', '1', '2'], accept)
  17     trie.AddToUncompressedTrie(uncompressed, ['0', '1', '2', '3'], accept)
  18     trie.AddToUncompressedTrie(uncompressed, ['0', '1', '3'], accept)
  19     trie.AddToUncompressedTrie(uncompressed, ['0', '1', '4'], accept)
  20     trie.AddToUncompressedTrie(uncompressed, ['0', '1', '5'], accept)
  21     return uncompressed
  22
  23   def CheckTrieAccepts(self, accept_sequences):
  24     accept = trie.AcceptInfo(input_rr='%eax', output_rr='%edx')
  25     self.assertEquals([(accept, ['0', '1', '2']),
  26                        (accept, ['0', '1', '2', '3']),
  27                        (accept, ['0', '1', '3']),
  28                        (accept, ['0', '1', '4']),
  29                        (accept, ['0', '1', '5'])],
  30                       accept_sequences)
  31
  32   def testTrieAddAndMerge(self):
  33     uncompressed = self.MakeUncompressedTrie()
  34     self.CheckTrieAccepts(trie.GetAllAcceptSequences(uncompressed))
  35     # n0 -0-> n1 -1-> n2 -2-> n3 -3-> n4
  36     #                  | -3-> n5
  37     #                  | -4-> n6
  38     #                  | -5-> n7
  39     self.assertEquals(8, len(trie.GetAllUniqueNodes(uncompressed)))
  40
  41     node_cache = trie.NodeCache()
  42     compressed_trie = node_cache.Merge(node_cache.empty_node, uncompressed)
  43     self.CheckTrieAccepts(trie.GetAllAcceptSequences(compressed_trie))
  44     # (n4, n5. n6, n7) can be grouped together from above
  45     self.assertEquals(5, len(trie.GetAllUniqueNodes(compressed_trie)))
  46
  47   def testTrieSerializationAndDeserialization(self):
  48     uncompressed = self.MakeUncompressedTrie()
  49     node_cache = trie.NodeCache()
  50     compressed_trie = node_cache.Merge(node_cache.empty_node, uncompressed)
  51     reconstructed_trie = trie.TrieFromDict(trie.TrieToDict(compressed_trie),
  52                                            node_cache)
  53     self.CheckTrieAccepts(trie.GetAllAcceptSequences(reconstructed_trie))
  54     self.assertEquals(5, len(trie.GetAllUniqueNodes(reconstructed_trie)))
  55
  56   def testTrieDiff(self):
  57     trie1 = trie.Node()
  58     trie2 = trie.Node()
  59     accept1 = trie.AcceptInfo(input_rr='%eax', output_rr='%edx')
  60     accept2 = trie.AcceptInfo(input_rr='%eax', output_rr='%ecx')
  61
  62     trie.AddToUncompressedTrie(trie1, ['0', '1', '2'], accept1)
  63     trie.AddToUncompressedTrie(trie1, ['0', '1', '3'], accept1)
  64     trie.AddToUncompressedTrie(trie1, ['0', '1', '4'], accept1)
  65     trie.AddToUncompressedTrie(trie1, ['0', '1', '5'], accept1)
  66
  67     trie.AddToUncompressedTrie(trie2, ['0', '1', '2'], accept1)
  68     trie.AddToUncompressedTrie(trie2, ['0', '1', '3'], accept1)
  69     trie.AddToUncompressedTrie(trie2, ['0', '1', '4'], accept2)
  70
  71     node_cache = trie.NodeCache()
  72     compressed_trie1 = node_cache.Merge(node_cache.empty_node, trie1)
  73     compressed_trie2 = node_cache.Merge(node_cache.empty_node, trie2)
  74
  75     diffs = set()
  76     compressed_diffs = set()
  77
  78     trie.DiffTries(trie1, trie2, node_cache.empty_node,
  79                    diffs.add, ())
  80     trie.DiffTries(compressed_trie1, compressed_trie2, node_cache.empty_node,
  81                    compressed_diffs.add, ())
  82
  83     self.assertEquals(
  84         diffs,
  85         set([(('0', '1', '4'), accept1, accept2),
  86              (('0', '1', '5'), accept1, None)]))
  87     self.assertEquals(diffs, compressed_diffs)
  88
  89
  90 if __name__ == '__main__':
  91   unittest.main()