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:isempty()
  66     return #self.stack == 0
  67   end
  68
  69   function Stack:dup()
  70     local new_stack = newobject(Stack)
  71     new_stack.stack = table_shallow_copy(self.stack)
  72     return new_stack
  73   end
  74
  75   function Stack:contains(elem)
  76     for e in each(self.stack) do
  77       if elem == e then
  78         return true
  79       end
  80     end
  81     return false
  82   end
  83
  84   function Stack:to_array()
  85     local arr = {}
  86     for i, val in ipairs(self.stack) do
  87       table.insert(arr, val)
  88     end
  89     return arr
  90   end
  91 -- class Stack
  92
  93
  94 -- Set
  95 Set = {name="Set"}
  96   function Set:new(init)
  97     local obj = newobject(self)
  98     obj.elements = {}
  99     if init then
 100       obj:add_collection(init)
 101     end
 102     return obj
 103   end
 104
 105   function Set:contains(x)
 106     return self.elements[x] ~= nil
 107   end
 108
 109   function Set:add(x)
 110     self.elements[x] = true
 111   end
 112
 113   function Set:remove(x)
 114     self.elements[x] = nil
 115   end
 116
 117   function Set:add_collection(arr)
 118     for elem in each(arr) do
 119       self:add(elem)
 120     end
 121   end
 122
 123   function Set:each()
 124     return pairs(self.elements)
 125   end
 126
 127   function Set:to_array()
 128     local arr = {}
 129     for elem in self:each() do
 130       table.insert(arr, elem)
 131     end
 132     return arr
 133   end
 134
 135   function Set:isempty()
 136     return self:count() == 0
 137   end
 138
 139   function Set:dup()
 140     local new_set = newobject(Set)
 141     new_set.elements = table_shallow_copy(self.elements)
 142     return new_set
 143   end
 144
 145   function Set:count()
 146     local i = 0
 147     for elem in self:each() do
 148       i = i + 1
 149     end
 150     return i
 151   end
 152
 153   function Set:hash_key()
 154     local arr = self:to_array()
 155     for i=1,#arr do
 156       arr[i] = tostring(arr[i])
 157     end
 158
 159     table.sort(arr)
 160
 161     str = "" for elem in each(arr) do str = str .. elem end
 162     return str
 163   end
 164 -- class Set
 165
 166 -- OrderedSet
 167 OrderedSet = {name="OrderedSet"}
 168   function OrderedSet:new(init)
 169     local obj = newobject(self)
 170     obj.element_offsets = {}
 171     obj.elements = {}
 172     if init then
 173       for element in each(init) do
 174         obj:add(element)
 175       end
 176     end
 177     return obj
 178   end
 179
 180   function OrderedSet:add(elem)
 181     if not self.element_offsets[elem] then
 182       table.insert(self.elements, elem)
 183       self.element_offsets[elem] = #self.elements
 184     end
 185   end
 186
 187   function OrderedSet:count()
 188     return #self.elements
 189   end
 190
 191   function OrderedSet:offset_of(elem)
 192     return self.element_offsets[elem]
 193   end
 194
 195   function OrderedSet:element_at(pos)
 196     return self.elements[pos]
 197   end
 198
 199   function OrderedSet:sort(sort_func)
 200     table.sort(self.elements, sort_func)
 201     self.element_offsets = {}
 202     for i, element in ipairs(self.elements) do
 203       self.element_offsets[element] = i
 204     end
 205   end
 206
 207   function OrderedSet:each()
 208     local i = 0
 209     return function ()
 210       i = i + 1
 211       if self.elements[i] then
 212         return self.elements[i]
 213       else
 214         return nil
 215       end
 216     end
 217   end
 218
 219 -- OrderedMap
 220 OrderedMap = {name="OrderedMap"}
 221   function OrderedMap:new()
 222     local obj = newobject(self)
 223     obj.key_offsets = {}
 224     obj.elements = {}
 225     return obj
 226   end
 227
 228   function OrderedMap:add(key, value)
 229     if not self.key_offsets[key] then
 230       table.insert(self.elements, {key, value})
 231       self.key_offsets[key] = #self.elements
 232     end
 233   end
 234
 235   function OrderedMap:get(key)
 236     return self.elements[self.key_offsets[key]][2]
 237   end
 238
 239   function OrderedMap:offset_of_key(elem)
 240     return self.key_offsets[elem]
 241   end
 242
 243   function OrderedMap:count()
 244     return #self.elements
 245   end
 246
 247   function OrderedMap:each()
 248     local i = 0
 249     return function ()
 250       i = i + 1
 251       if self.elements[i] then
 252         return unpack(self.elements[i])
 253       else
 254         return nil
 255       end
 256     end
 257   end
 258
 259 -- Range
 260 -- The Range is *inclusive* at both ends.
 261 Range = {name="Range"}
 262   function Range:new(low, high)
 263     assert(low <= high)
 264
 265     local obj = newobject(self)
 266     obj.low = low
 267     obj.high = high
 268     return obj
 269   end
 270
 271   function Range.union(a, b)
 272     if math.max(a.low, b.low) <= (math.min(a.high, b.high)+1) then
 273       return Range:new(math.min(a.low, b.low), math.max(a.high, b.high))
 274     else
 275       return nil
 276     end
 277   end
 278
 279   function Range:contains(int)
 280     return (self.low <= int) and (self.high >= int)
 281   end
 282
 283   function Range:tostring(display_val_func)
 284     if self.low == self.high then
 285       return display_val_func(self.low)
 286     else
 287       return display_val_func(self.low) .. "-" .. display_val_func(self.high)
 288     end
 289   end
 290 -- class Range
 291
 292
 293 -- IntSet
 294 -- None of the ranges may overlap.
 295 IntSet = {name="IntSet"}
 296   function IntSet:new()
 297     local obj = newobject(self)
 298     obj.list = {}
 299     obj.negated = false
 300     return obj
 301   end
 302
 303   function IntSet:add(new_range)
 304     local newlist = {}
 305     for range in each(self.list) do
 306       local union = new_range:union(range)
 307       if union then
 308         new_range = union
 309       else
 310         table.insert(newlist, range)
 311       end
 312     end
 313
 314     table.insert(newlist, new_range)
 315     self.list = newlist
 316   end
 317
 318   function IntSet:get_non_negated()
 319     if self.negated then
 320       return self:invert()
 321     else
 322       return self
 323     end
 324   end
 325
 326   -- This is O(n^2) right now, and can probably
 327   -- be made O(n lg n) with a little thought, but n's
 328   -- are so small right now that I won't worry.
 329   function IntSet:add_intset(intset)
 330     for range in each(intset.list) do
 331       self:add(range)
 332     end
 333   end
 334
 335   function IntSet:contains(int)
 336     local obj = self:get_non_negated()
 337     for range in each(obj.list) do
 338       if range:contains(int) then return true end
 339     end
 340     return false
 341   end
 342
 343   function IntSet:sampleint()
 344     local obj = self:get_non_negated()
 345
 346     if #obj.list == 0 then
 347       return nil
 348     else
 349       return obj.list[1].low
 350     end
 351   end
 352
 353   function IntSet:invert()
 354     local new_intset = IntSet:new()
 355     new_intset.negated = not self.negated
 356
 357     table.sort(self.list, function (a, b) return a.low < b.low end)
 358     local offset = 0
 359
 360     for range in each(self.list) do
 361       if offset <= range.low-1 then
 362         new_intset:add(Range:new(offset, range.low-1))
 363       end
 364       offset = range.high+1
 365     end
 366
 367     if offset ~= math.huge then
 368       new_intset:add(Range:new(offset, math.huge))
 369     end
 370
 371     return new_intset
 372   end
 373
 374   function IntSet:each_range()
 375     return each(self:get_non_negated().list)
 376   end
 377
 378   function IntSet:isunbounded()
 379     for range in each(self.list) do
 380       if range.high == math.huge then
 381         return true
 382       end
 383     end
 384     return false
 385   end
 386
 387   function IntSet:tostring(display_val_func)
 388     local str = ""
 389     if self.negated then str = "^" end
 390
 391     table.sort(self.list, function (a, b) return a.low < b.low end)
 392     local first = true
 393     for range in each(self.list) do
 394       if first then
 395         first = false
 396       else
 397         str = str .. ","
 398       end
 399
 400       str = str .. range:tostring(display_val_func)
 401     end
 402
 403     return str
 404   end
 405
 406   function IntSet:toasciistring()
 407     local convert_func = function (x)
 408       if x == math.huge then
 409         return "del"
 410       elseif x < 33 then
 411         return string.format("\\%03o", x)
 412       else
 413         return string.char(x)
 414       end
 415     end
 416     return self:tostring(convert_func)
 417   end
 418
 419   function IntSet:tointstring()
 420     return self:tostring(function (x) return tostring(x) end)
 421   end
 422 -- class IntSet
 423
 424 ShallowTable = {name="ShallowTable"}
 425 function ShallowTable:new(val)
 426   if val == nil then return nil end
 427
 428   if not self.cache then
 429     self.cache = {}
 430     --setmetatable(self.cache, {__mode = "v"})  -- make values weak
 431   end
 432
 433   local str = ""
 434   local keys = {}
 435   for key in pairs(val) do table.insert(keys, key) end
 436   table.sort(keys)
 437   for key in each(keys) do
 438     if type(val[key]) == "table" and val[key].class == fa.NonTerm then
 439       str = str .. "|" .. key .. ":NONTERM" .. tostring(val[key].name)
 440     else
 441       str = str .. "|" .. key .. ":" .. tostring(val[key])
 442     end
 443   end
 444
 445   if not self.cache[str] then
 446     self.cache[str] = newobject(self)
 447     for k,v in pairs(val) do
 448       self.cache[str][k] = v
 449     end
 450   end
 451
 452   return self.cache[str]
 453 end
 454
 455 -- vim:et:sts=2:sw=2