compiler/misc.lua

   1 --[[--------------------------------------------------------------------
   2
   3   Gazelle: a system for building fast, reusable parsers
   4
   5   misc.lua
   6
   7   Miscellaneous algorithms that don't belong anywhere else.
   8
   9   Copyright (c) 2007-2008 Joshua Haberman.  See LICENSE for details.
  10
  11 --------------------------------------------------------------------]]--
  12
  13 function newobject(class)
  14   local obj = {}
  15   setmetatable(obj, class)
  16   obj.class = class
  17   class.__index = class
  18   return obj
  19 end
  20
  21 -- each(foo): returns an iterator; if the object supports the each method,
  22 --            call that, otherwise return an iterator for a plain array.
  23 function each(array_or_eachable_obj)
  24   if array_or_eachable_obj.class then
  25     return array_or_eachable_obj:each()
  26   else
  27     local array = array_or_eachable_obj
  28     local i = 0
  29     return function ()
  30       i = i + 1
  31       if array[i] then return array[i] else return nil end
  32     end
  33   end
  34 end
  35
  36 function table_shallow_eql(tbl1, tbl2)
  37   for k,v in pairs(tbl1) do
  38     if tbl1[k] ~= tbl2[k] then return false end
  39   end
  40   for k,v in pairs(tbl2) do
  41     if tbl1[k] ~= tbl2[k] then return false end
  42   end
  43   return true
  44 end
  45
  46 function table_copy(t, max_depth)
  47   local new_t = {}
  48   for k, v in pairs(t) do
  49     if max_depth > 1 and type(v) == "table" then
  50       v = table_copy(v, max_depth - 1)
  51     end
  52     new_t[k] = v
  53   end
  54   return new_t
  55 end
  56
  57 function table_shallow_copy(t)
  58   return table_copy(t, 1)
  59 end
  60
  61 function get_common_prefix_len(arrays)
  62   local common_len = 0
  63   while common_len <= #arrays[1] do
  64     local elem = arrays[1][common_len+1]
  65     for array in each(arrays) do
  66       if array[common_len+1] ~= elem then
  67         return common_len
  68       end
  69     end
  70     common_len = common_len + 1
  71   end
  72   return common_len
  73 end
  74
  75 cache = {}
  76 function get_unique_table_for(val)
  77   local string_table = {}
  78   for entry in each(val) do table.insert(string_table, tostring(entry)) end
  79   local str = table.concat(string_table, "\136")
  80   if not cache[str] then
  81     cache[str] = table_shallow_copy(val)
  82   end
  83   return cache[str]
  84 end
  85
  86 function depth_first_traversal(obj, children_func)
  87   local seen = Set:new{obj}
  88   local stack = Stack:new()
  89   stack:push(obj)
  90   depth_first_traversal_helper(obj, children_func, stack, seen)
  91   return seen
  92 end
  93
  94 function depth_first_traversal_helper(obj, children_func, stack, seen)
  95   local children = children_func(obj, stack) or {}
  96   for child in each(children) do
  97     if not seen:contains(child) then
  98       seen:add(child)
  99       stack:push(child)
 100       depth_first_traversal_helper(child, children_func, stack, seen)
 101       stack:pop()
 102     end
 103   end
 104 end
 105
 106 -- all ints within each IntSet are assumed to be equivalent.
 107 -- Given this, return a new list of IntSets, where each IntSet
 108 -- returned is considered equivalent across ALL IntSets.
 109 function equivalence_classes(int_sets)
 110   local BEGIN = 0
 111   local END = 1
 112
 113   local events = {}
 114   for int_set in each(int_sets) do
 115     if int_set.negated then int_set = int_set:invert() end
 116     for range in each(int_set.list) do
 117       table.insert(events, {range.low, BEGIN, int_set})
 118       table.insert(events, {range.high+1, END, int_set})
 119     end
 120   end
 121
 122   local cmp_events = function(a, b)
 123     if a[1] == b[1] then
 124       return b[2] < a[2]   -- END events should go before BEGIN events
 125     else
 126       return a[1] < b[1]
 127     end
 128   end
 129
 130   table.sort(events, cmp_events)
 131
 132   local nested_regions = Set:new()
 133   local last_offset = nil
 134   classes = {}
 135   for event in each(events) do
 136     local offset, event_type, int_set = unpack(event)
 137
 138     if last_offset and last_offset < offset and (not nested_regions:isempty()) then
 139       local hk = nested_regions:hash_key()
 140       classes[hk] = classes[hk] or IntSet:new()
 141       classes[hk]:add(Range:new(last_offset, offset-1))
 142     end
 143
 144     if event_type == BEGIN then
 145       nested_regions:add(int_set)
 146     else
 147       nested_regions:remove(int_set)
 148     end
 149     last_offset = offset
 150   end
 151
 152   local ret = {}
 153   for hk, int_set in pairs(classes) do
 154     table.insert(ret, int_set)
 155   end
 156   return ret
 157 end
 158
 159 function str_join(list, separator)
 160   local str = ""
 161   for i, string in ipairs(list) do
 162     str = str .. string
 163     if i < #list then
 164       str = str .. separator
 165     end
 166   end
 167   return str
 168 end
 169
 170 function table_contains(table, element)
 171   for i, table_element in pairs(table) do
 172     if element == table_element then
 173       return true
 174     end
 175   end
 176   return false
 177 end
 178
 179 function clamp_table(tab, len)
 180   local my_table = table_shallow_copy(tab)
 181   while #my_table > len do
 182     table.remove(my_table)
 183   end
 184   return my_table
 185 end
 186
 187 -- vim:et:sts=2:sw=2