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 cache = {}
  62 function get_unique_table_for(val)
  63   local string_table = {}
  64   for entry in each(val) do table.insert(string_table, tostring(entry)) end
  65   local str = table.concat(string_table, "\136")
  66   if not cache[str] then
  67     cache[str] = table_shallow_copy(val)
  68   end
  69   return cache[str]
  70 end
  71
  72 -- traverses a graph of some sort -- caller provides a function that gives
  73 -- children of the current node.
  74 function breadth_first_traversal(obj, children_func)
  75   local seen = Set:new{obj}
  76   local queue = Queue:new(obj)
  77   while not queue:isempty() do
  78     local node = queue:dequeue()
  79     children = children_func(node) or {}
  80     for child_node in each(children) do
  81       if seen:contains(child_node) == false then
  82         seen:add(child_node)
  83         queue:enqueue(child_node)
  84       end
  85     end
  86   end
  87   return seen
  88 end
  89
  90 function depth_first_traversal(obj, children_func)
  91   local seen = Set:new{obj}
  92   local stack = Stack:new()
  93   stack:push(obj)
  94   depth_first_traversal_helper(obj, children_func, stack, seen)
  95 end
  96
  97 function depth_first_traversal_helper(obj, children_func, stack, seen)
  98   children = children_func(obj, stack) or {}
  99   for child in each(children) do
 100     if not seen:contains(child) then
 101       seen:add(child)
 102       stack:push(child)
 103       depth_first_traversal_helper(child, children_func, stack, seen)
 104       stack:pop()
 105     end
 106   end
 107 end
 108
 109 -- all ints within each IntSet are assumed to be equivalent.
 110 -- Given this, return a new list of IntSets, where each IntSet
 111 -- returned is considered equivalent across ALL IntSets.
 112 function equivalence_classes(int_sets)
 113   local BEGIN = 0
 114   local END = 1
 115
 116   local events = {}
 117   for int_set in each(int_sets) do
 118     if int_set.negated then int_set = int_set:invert() end
 119     for range in each(int_set.list) do
 120       table.insert(events, {range.low, BEGIN, int_set})
 121       table.insert(events, {range.high+1, END, int_set})
 122     end
 123   end
 124
 125   local cmp_events = function(a, b)
 126     if a[1] == b[1] then
 127       return b[2] < a[2]   -- END events should go before BEGIN events
 128     else
 129       return a[1] < b[1]
 130     end
 131   end
 132
 133   table.sort(events, cmp_events)
 134
 135   local nested_regions = Set:new()
 136   local last_offset = nil
 137   classes = {}
 138   for event in each(events) do
 139     local offset, event_type, int_set = unpack(event)
 140
 141     if last_offset and last_offset < offset and (not nested_regions:isempty()) then
 142       local hk = nested_regions:hash_key()
 143       classes[hk] = classes[hk] or IntSet:new()
 144       classes[hk]:add(Range:new(last_offset, offset-1))
 145     end
 146
 147     if event_type == BEGIN then
 148       nested_regions:add(int_set)
 149     else
 150       nested_regions:remove(int_set)
 151     end
 152     last_offset = offset
 153   end
 154
 155   local ret = {}
 156   for hk, int_set in pairs(classes) do
 157     table.insert(ret, int_set)
 158   end
 159   return ret
 160 end
 161
 162 function str_join(list, separator)
 163   local str = ""
 164   for i, string in ipairs(list) do
 165     str = str .. string
 166     if i < #list then
 167       str = str .. separator
 168     end
 169   end
 170   return str
 171 end
 172
 173 -- vim:et:sts=2:sw=2