compiler/data_structures.lua

   1 --[[--------------------------------------------------------------------
   2
   3   Gazelle: a system for building fast, reusable parsers
   4
   5   data_structures.lua
   6
   7   Implementations of useful data structures that we use often.
   8   Most of these are just useful interfaces around Lua's tables.
   9
  10   Copyright (c) 2007 Joshua Haberman.  See LICENSE for details.
  11
  12 --------------------------------------------------------------------]]--
  13
  14 require "misc"
  15
  16 -- Queue
  17 Queue = {name="Queue"}
  18   function Queue:new(init)
  19     local obj = newobject(self)
  20     obj.first = 0
  21     obj.last  = -1
  22     if init then obj:enqueue(init) end
  23     return obj
  24   end
  25
  26   function Queue:enqueue(val)
  27     self.last = self.last + 1
  28     self[self.last] = val
  29   end
  30
  31   function Queue:dequeue()
  32     if self:isempty() then error("Tried to dequeue an empty queue") end
  33     local val = self[self.first]
  34     self[self.first] = nil
  35     self.first = self.first + 1
  36     return val
  37   end
  38
  39   function Queue:isempty()
  40     return self.first > self.last
  41   end
  42 -- class Queue
  43
  44
  45 -- Stack
  46 Stack = {name="Stack"}
  47   function Stack:new(init)
  48     local obj = newobject(self)
  49     obj.stack = {}
  50     return obj
  51   end
  52
  53   function Stack:push(val)
  54     table.insert(self.stack, val)
  55   end
  56
  57   function Stack:pop()
  58     return table.remove(self.stack)
  59   end
  60
  61   function Stack:top()
  62     return self.stack[#self.stack]
  63   end
  64
  65   function Stack:contains(elem)
  66     for e in each(self.stack) do
  67       if elem == e then
  68         return true
  69       end
  70     end
  71     return false
  72   end
  73
  74   function Stack:to_array()
  75     local arr = {}
  76     for i, val in ipairs(self.stack) do
  77       table.insert(arr, val)
  78     end
  79     return arr
  80   end
  81 -- class Stack
  82
  83
  84 -- Set
  85 Set = {name="Set"}
  86   function Set:new(init)
  87     local obj = newobject(self)
  88     obj.elements = {}
  89     if init then
  90       obj:add_collection(init)
  91     end
  92     return obj
  93   end
  94
  95   function Set:contains(x)
  96     return self.elements[x] ~= nil
  97   end
  98
  99   function Set:add(x)
 100     self.elements[x] = true
 101   end
 102
 103   function Set:remove(x)
 104     self.elements[x] = nil
 105   end
 106
 107   function Set:add_collection(arr)
 108     for elem in each(arr) do
 109       self:add(elem)
 110     end
 111   end
 112
 113   function Set:each()
 114     return pairs(self.elements)
 115   end
 116
 117   function Set:to_array()
 118     local arr = {}
 119     for elem in self:each() do
 120       table.insert(arr, elem)
 121     end
 122     return arr
 123   end
 124
 125   function Set:isempty()
 126     return self:count() == 0
 127   end
 128
 129   function Set:count()
 130     local i = 0
 131     for elem in self:each() do
 132       i = i + 1
 133     end
 134     return i
 135   end
 136
 137   function Set:hash_key()
 138     local arr = self:to_array()
 139     for i=1,#arr do
 140       arr[i] = tostring(arr[i])
 141     end
 142
 143     table.sort(arr)
 144
 145     str = "" for elem in each(arr) do str = str .. elem end
 146     return str
 147   end
 148 -- class Set
 149
 150 -- OrderedSet
 151 OrderedSet = {name="OrderedSet"}
 152   function OrderedSet:new(init)
 153     local obj = newobject(self)
 154     obj.element_offsets = {}
 155     obj.elements = {}
 156     if init then
 157       for element in each(init) do
 158         self:add(element)
 159       end
 160     end
 161     return obj
 162   end
 163
 164   function OrderedSet:add(elem)
 165     if not self.element_offsets[elem] then
 166       self.element_offsets[elem] = #self.elements
 167       table.insert(self.element, elem)
 168     end
 169   end
 170
 171   function OrderedSet:offset_of(elem)
 172     return self.element_offsets[elem]
 173   end
 174
 175   function OrderedSet:each()
 176     local i = 0
 177     return function ()
 178       i = i + 1
 179       if self.elements[i] then
 180         return self.elements[i]
 181       else
 182         return nil
 183       end
 184     end
 185   end
 186
 187 -- OrderedMap
 188 OrderedMap = {name="OrderedMap"}
 189   function OrderedMap:new()
 190     local obj = newobject(self)
 191     obj.key_offsets = {}
 192     obj.elements = {}
 193     return obj
 194   end
 195
 196   function OrderedMap:add(key, value)
 197     if not self.key_offsets[key] then
 198       self.key_offsets[key] = #self.elements
 199       table.insert(self.elements, {key, value})
 200     end
 201   end
 202
 203   function OrderedMap:get(key)
 204     return self.elements[self.key_offsets[key]][2]
 205   end
 206
 207   function OrderedMap:offset_of_key(elem)
 208     return self.key_offsets[elem]
 209   end
 210
 211   function OrderedMap:each()
 212     local i = 0
 213     return function ()
 214       i = i + 1
 215       if self.elements[i] then
 216         return unpack(self.elements[i])
 217       else
 218         return nil
 219       end
 220     end
 221   end
 222
 223 -- Range
 224 -- The Range is *inclusive* at both ends.
 225 Range = {name="Range"}
 226   function Range:new(low, high)
 227     assert(low <= high)
 228
 229     local obj = newobject(self)
 230     obj.low = low
 231     obj.high = high
 232     return obj
 233   end
 234
 235   function Range.union(a, b)
 236     if math.max(a.low, b.low) <= (math.min(a.high, b.high)+1) then
 237       return Range:new(math.min(a.low, b.low), math.max(a.high, b.high))
 238     else
 239       return nil
 240     end
 241   end
 242
 243   function Range:contains(int)
 244     return (self.low <= int) and (self.high >= int)
 245   end
 246
 247   function Range:tostring(display_val_func)
 248     if self.low == self.high then
 249       return display_val_func(self.low)
 250     else
 251       return display_val_func(self.low) .. "-" .. display_val_func(self.high)
 252     end
 253   end
 254 -- class Range
 255
 256
 257 -- IntSet
 258 -- None of the ranges may overlap.
 259 IntSet = {name="IntSet"}
 260   function IntSet:new()
 261     local obj = newobject(self)
 262     obj.list = {}
 263     obj.negated = false
 264     return obj
 265   end
 266
 267   function IntSet:add(new_range)
 268     local newlist = {}
 269     for range in each(self.list) do
 270       local union = new_range:union(range)
 271       if union then
 272         new_range = union
 273       else
 274         table.insert(newlist, range)
 275       end
 276     end
 277
 278     table.insert(newlist, new_range)
 279     self.list = newlist
 280   end
 281
 282   function IntSet:get_non_negated()
 283     if self.negated then
 284       return self:invert()
 285     else
 286       return self
 287     end
 288   end
 289
 290   -- This is O(n^2) right now, and can probably
 291   -- be made O(n lg n) with a little thought, but n's
 292   -- are so small right now that I won't worry.
 293   function IntSet:add_intset(intset)
 294     for range in each(intset.list) do
 295       self:add(range)
 296     end
 297   end
 298
 299   function IntSet:contains(int)
 300     local obj = self:get_non_negated()
 301     for range in each(obj.list) do
 302       if range:contains(int) then return true end
 303     end
 304     return false
 305   end
 306
 307   function IntSet:sampleint()
 308     local obj = self:get_non_negated()
 309
 310     if #obj.list == 0 then
 311       return nil
 312     else
 313       return obj.list[1].low
 314     end
 315   end
 316
 317   function IntSet:invert()
 318     local new_intset = IntSet:new()
 319     new_intset.negated = not self.negated
 320
 321     table.sort(self.list, function (a, b) return a.low < b.low end)
 322     local offset = 0
 323
 324     for range in each(self.list) do
 325       if offset <= range.low-1 then
 326         new_intset:add(Range:new(offset, range.low-1))
 327       end
 328       offset = range.high+1
 329     end
 330
 331     if offset ~= math.huge then
 332       new_intset:add(Range:new(offset, math.huge))
 333     end
 334
 335     return new_intset
 336   end
 337
 338   function IntSet:each_range()
 339     return each(self:get_non_negated().list)
 340   end
 341
 342   function IntSet:isunbounded()
 343     for range in each(self.list) do
 344       if range.high == math.huge then
 345         return true
 346       end
 347     end
 348     return false
 349   end
 350
 351   function IntSet:tostring(display_val_func)
 352     local str = ""
 353     if self.negated then str = "^" end
 354
 355     table.sort(self.list, function (a, b) return a.low < b.low end)
 356     local first = true
 357     for range in each(self.list) do
 358       if first then
 359         first = false
 360       else
 361         str = str .. ","
 362       end
 363
 364       str = str .. range:tostring(display_val_func)
 365     end
 366
 367     return str
 368   end
 369
 370   function IntSet:toasciistring()
 371     local convert_func = function (x)
 372       if x == math.huge then
 373         return "del"
 374       elseif x < 33 then
 375         return string.format("\\%03o", x)
 376       else
 377         return string.char(x)
 378       end
 379     end
 380     return self:tostring(convert_func)
 381   end
 382
 383   function IntSet:tointstring()
 384     return self:tostring(function (x) return tostring(x) end)
 385   end
 386 -- class IntSet
 387
 388 ShallowTable = {name="ShallowTable"}
 389 function ShallowTable:new(val)
 390   if val == nil then return nil end
 391
 392   if not self.cache then
 393     self.cache = {}
 394     --setmetatable(self.cache, {__mode = "v"})  -- make values weak
 395   end
 396
 397   local str = ""
 398   local keys = {}
 399   for key in pairs(val) do table.insert(keys, key) end
 400   table.sort(keys)
 401   for key in each(keys) do
 402     if type(val[key]) == "table" and val[key].class == fa.NonTerm then
 403       str = str .. "|" .. key .. ":NONTERM" .. tostring(val[key].name)
 404     else
 405       str = str .. "|" .. key .. ":" .. tostring(val[key])
 406     end
 407   end
 408
 409   if not self.cache[str] then
 410     self.cache[str] = newobject(self)
 411     for k,v in pairs(val) do
 412       self.cache[str][k] = v
 413     end
 414   end
 415
 416   return self.cache[str]
 417 end
 418
 419 -- vim:et:sts=2:sw=2