minify/optparser.lua

--[[--------------------------------------------------------------------

  optparser.lua: does parser-based optimizations

  This file is part of LuaSrcDiet.

  Copyright (c) 2008 Kein-Hong Man <khman@users.sf.net>

  The COPYRIGHT file describes the conditions

  under which this software may be distributed.

  See the ChangeLog for more information.

----------------------------------------------------------------------]]

--[[--------------------------------------------------------------------

-- NOTES:

-- * For more parser-based optimization ideas, see the TODO items or

--   look at technotes.txt.

-- * The processing load is quite significant, but since this is an

--   off-line text processor, I believe we can wait a few seconds.

-- * TODO: might process "local a,a,a" wrongly... need tests!

-- * TODO: remove position handling if overlapped locals (rem < 0)

--   needs more study, to check behaviour

-- * TODO: there are probably better ways to do allocation, e.g. by

--   choosing better methods to sort and pick locals...

-- * TODO: we don't need 53*63 two-letter identifiers; we can make

--   do with significantly less depending on how many that are really

--   needed and improve entropy; e.g. 13 needed -> choose 4*4 instead

----------------------------------------------------------------------]]

local base = _G

local string = require "string"

local table = require "table"

----------------------------------------------------------------------

-- Letter frequencies for reducing symbol entropy (fixed version)

-- * Might help a wee bit when the output file is compressed

-- * See Wikipedia: http://en.wikipedia.org/wiki/Letter_frequencies

-- * We use letter frequencies according to a Linotype keyboard, plus

--   the underscore, and both lower case and upper case letters.

-- * The arrangement below (LC, underscore, %d, UC) is arbitrary.

-- * This is certainly not optimal, but is quick-and-dirty and the

--   process has no significant overhead

----------------------------------------------------------------------

local LETTERS = "etaoinshrdlucmfwypvbgkqjxz_ETAOINSHRDLUCMFWYPVBGKQJXZ"

local ALPHANUM = "etaoinshrdlucmfwypvbgkqjxz_0123456789ETAOINSHRDLUCMFWYPVBGKQJXZ"

-- names or identifiers that must be skipped

-- * the first two lines are for keywords

local SKIP_NAME = {}

for v in string.gmatch([[

and break do else elseif end false for function if in

local nil not or repeat return then true until while

self _ENV]], "%S+") do

  SKIP_NAME[v] = true

end

------------------------------------------------------------------------

-- variables and data structures

------------------------------------------------------------------------

local toklist, seminfolist,             -- token lists

      globalinfo, localinfo,            -- variable information tables

      globaluniq, localuniq,            -- unique name tables

      var_new,                          -- index of new variable names

      varlist                           -- list of output variables

----------------------------------------------------------------------

-- preprocess information table to get lists of unique names

----------------------------------------------------------------------

local function preprocess(infotable)

  local uniqtable = {}

  for i = 1, #infotable do              -- enumerate info table

    local obj = infotable[i]

    local name = obj.name

    --------------------------------------------------------------------

    if not uniqtable[name] then         -- not found, start an entry

      uniqtable[name] = {

        decl = 0, token = 0, size = 0,

      }

    end

    --------------------------------------------------------------------

    local uniq = uniqtable[name]        -- count declarations, tokens, size

    uniq.decl = uniq.decl + 1

    local xref = obj.xref

    local xcount = #xref

    uniq.token = uniq.token + xcount

    uniq.size = uniq.size + xcount * #name

    --------------------------------------------------------------------

    if obj.decl then            -- if local table, create first,last pairs

      obj.id = i

      obj.xcount = xcount

      if xcount > 1 then        -- if ==1, means local never accessed

        obj.first = xref[2]

        obj.last = xref[xcount]

      end

    --------------------------------------------------------------------

    else                        -- if global table, add a back ref

      uniq.id = i

    end

    --------------------------------------------------------------------

  end--for

  return uniqtable

end

----------------------------------------------------------------------

-- calculate actual symbol frequencies, in order to reduce entropy

-- * this may help further reduce the size of compressed sources

-- * note that since parsing optimizations is put before lexing

--   optimizations, the frequency table is not exact!

-- * yes, this will miss --keep block comments too...

----------------------------------------------------------------------

local function recalc_for_entropy(option)

  local byte = string.byte

  local char = string.char

  -- table of token classes to accept in calculating symbol frequency

  local ACCEPT = {

    TK_KEYWORD = true, TK_NAME = true, TK_NUMBER = true,

    TK_STRING = true, TK_LSTRING = true,

  }

  if not option["opt-comments"] then

    ACCEPT.TK_COMMENT = true

    ACCEPT.TK_LCOMMENT = true

  end

  --------------------------------------------------------------------

  -- create a new table and remove any original locals by filtering

  --------------------------------------------------------------------

  local filtered = {}

  for i = 1, #toklist do

    filtered[i] = seminfolist[i]

  end

  for i = 1, #localinfo do              -- enumerate local info table

    local obj = localinfo[i]

    local xref = obj.xref

    for j = 1, obj.xcount do

      local p = xref[j]

      filtered[p] = ""                  -- remove locals

    end

  end

  --------------------------------------------------------------------

  local freq = {}                       -- reset symbol frequency table

  for i = 0, 255 do freq[i] = 0 end

  for i = 1, #toklist do                -- gather symbol frequency

    local tok, info = toklist[i], filtered[i]

    if ACCEPT[tok] then

      for j = 1, #info do

        local c = byte(info, j)

        freq[c] = freq[c] + 1

      end

    end--if

  end--for

  --------------------------------------------------------------------

  -- function to re-sort symbols according to actual frequencies

  --------------------------------------------------------------------

  local function resort(symbols)

    local symlist = {}

    for i = 1, #symbols do              -- prepare table to sort

      local c = byte(symbols, i)

      symlist[i] = { c = c, freq = freq[c], }

    end

    table.sort(symlist,                 -- sort selected symbols

      function(v1, v2)

        return v1.freq > v2.freq

      end

    )

    local charlist = {}                 -- reconstitute the string

    for i = 1, #symlist do

      charlist[i] = char(symlist[i].c)

    end

    return table.concat(charlist)

  end

  --------------------------------------------------------------------

  LETTERS = resort(LETTERS)             -- change letter arrangement

  ALPHANUM = resort(ALPHANUM)

end

----------------------------------------------------------------------

-- returns a string containing a new local variable name to use, and

-- a flag indicating whether it collides with a global variable

-- * trapping keywords and other names like 'self' is done elsewhere

----------------------------------------------------------------------

local function new_var_name()

  local var

  local cletters, calphanum = #LETTERS, #ALPHANUM

  local v = var_new

  if v < cletters then                  -- single char

    v = v + 1

    var = string.sub(LETTERS, v, v)

  else                                  -- longer names

    local range, sz = cletters, 1       -- calculate # chars fit

    repeat

      v = v - range

      range = range * calphanum

      sz = sz + 1

    until range > v

    local n = v % cletters              -- left side cycles faster

    v = (v - n) / cletters              -- do first char first

    n = n + 1

    var = string.sub(LETTERS, n, n)

    while sz > 1 do

      local m = v % calphanum

      v = (v - m) / calphanum

      m = m + 1

      var = var..string.sub(ALPHANUM, m, m)

      sz = sz - 1

    end

  end

  var_new = var_new + 1

  return var, globaluniq[var] ~= nil

end

----------------------------------------------------------------------

-- main entry point

-- * does only local variable optimization for now

----------------------------------------------------------------------

function optimize(option, _toklist, _seminfolist, _globalinfo, _localinfo)

  -- set tables

  toklist, seminfolist, globalinfo, localinfo

    = _toklist, _seminfolist, _globalinfo, _localinfo

  var_new = 0                           -- reset variable name allocator

  varlist = {}

  ------------------------------------------------------------------

  -- preprocess global/local tables, handle entropy reduction

  ------------------------------------------------------------------

  globaluniq = preprocess(globalinfo)

  localuniq = preprocess(localinfo)

  if option["opt-entropy"] then         -- for entropy improvement

    recalc_for_entropy(option)

  end

  ------------------------------------------------------------------

  -- build initial declared object table, then sort according to

  -- token count, this might help assign more tokens to more common

  -- variable names such as 'e' thus possibly reducing entropy

  -- * an object knows its localinfo index via its 'id' field

  -- * special handling for "self" special local (parameter) here

  ------------------------------------------------------------------

  local object = {}

  for i = 1, #localinfo do

    object[i] = localinfo[i]

  end

  table.sort(object,                    -- sort largest first

    function(v1, v2)

      return v1.xcount > v2.xcount

    end

  )

  ------------------------------------------------------------------

  -- the special "self" function parameters must be preserved

  -- * the allocator below will never use "self", so it is safe to

  --   keep those implicit declarations as-is

  ------------------------------------------------------------------

  local temp, j, gotself = {}, 1, false

  for i = 1, #object do

    local obj = object[i]

    if not obj.preserve then

      temp[j] = obj

      j = j + 1

    elseif obj.name == "self" then

      gotself = true

    end

  end

  object = temp

  ------------------------------------------------------------------

  -- a simple first-come first-served heuristic name allocator,

  -- note that this is in no way optimal...

  -- * each object is a local variable declaration plus existence

  -- * the aim is to assign short names to as many tokens as possible,

  --   so the following tries to maximize name reuse

  -- * note that we preserve sort order

  ------------------------------------------------------------------

  local nobject = #object

  while nobject > 0 do

    local varname, gcollide

    repeat

      varname, gcollide = new_var_name()  -- collect a variable name

    until not SKIP_NAME[varname]          -- skip all special names

    varlist[#varlist + 1] = varname       -- keep a list

    local oleft = nobject

    ------------------------------------------------------------------

    -- if variable name collides with an existing global, the name

    -- cannot be used by a local when the name is accessed as a global

    -- during which the local is alive (between 'act' to 'rem'), so

    -- we drop objects that collides with the corresponding global

    ------------------------------------------------------------------

    if gcollide then

      -- find the xref table of the global

      local gref = globalinfo[globaluniq[varname].id].xref

      local ngref = #gref

      -- enumerate for all current objects; all are valid at this point

      for i = 1, nobject do

        local obj = object[i]

        local act, rem = obj.act, obj.rem  -- 'live' range of local

        -- if rem < 0, it is a -id to a local that had the same name

        -- so follow rem to extend it; does this make sense?

        while rem < 0 do

          rem = localinfo[-rem].rem

        end

        local drop

        for j = 1, ngref do

          local p = gref[j]

          if p >= act and p <= rem then drop = true end  -- in range?

        end

        if drop then

          obj.skip = true

          oleft = oleft - 1

        end

      end--for

    end--if gcollide

    ------------------------------------------------------------------

    -- now the first unassigned local (since it's sorted) will be the

    -- one with the most tokens to rename, so we set this one and then

    -- eliminate all others that collides, then any locals that left

    -- can then reuse the same variable name; this is repeated until

    -- all local declaration that can use this name is assigned

    -- * the criteria for local-local reuse/collision is:

    --   A is the local with a name already assigned

    --   B is the unassigned local under consideration

    --   => anytime A is accessed, it cannot be when B is 'live'

    --   => to speed up things, we have first/last accesses noted

    ------------------------------------------------------------------

    while oleft > 0 do

      local i = 1

      while object[i].skip do  -- scan for first object

        i = i + 1

      end

      ------------------------------------------------------------------

      -- first object is free for assignment of the variable name

      -- [first,last] gives the access range for collision checking

      ------------------------------------------------------------------

      oleft = oleft - 1

      local obja = object[i]

      i = i + 1

      obja.newname = varname

      obja.skip = true

      obja.done = true

      local first, last = obja.first, obja.last

      local xref = obja.xref

      ------------------------------------------------------------------

      -- then, scan all the rest and drop those colliding

      -- if A was never accessed then it'll never collide with anything

      -- otherwise trivial skip if:

      -- * B was activated after A's last access (last < act)

      -- * B was removed before A's first access (first > rem)

      -- if not, see detailed skip below...

      ------------------------------------------------------------------

      if first and oleft > 0 then  -- must have at least 1 access

        local scanleft = oleft

        while scanleft > 0 do

          while object[i].skip do  -- next valid object

            i = i + 1

          end

          scanleft = scanleft - 1

          local objb = object[i]

          i = i + 1

          local act, rem = objb.act, objb.rem  -- live range of B

          -- if rem < 0, extend range of rem thru' following local

          while rem < 0 do

            rem = localinfo[-rem].rem

          end

          --------------------------------------------------------

          if not(last < act or first > rem) then  -- possible collision

            --------------------------------------------------------

            -- B is activated later than A or at the same statement,

            -- this means for no collision, A cannot be accessed when B

            -- is alive, since B overrides A (or is a peer)

            --------------------------------------------------------

            if act >= obja.act then

              for j = 1, obja.xcount do  -- ... then check every access

                local p = xref[j]

                if p >= act and p <= rem then  -- A accessed when B live!

                  oleft = oleft - 1

                  objb.skip = true

                  break

                end

              end--for

            --------------------------------------------------------

            -- A is activated later than B, this means for no collision,

            -- A's access is okay since it overrides B, but B's last

            -- access need to be earlier than A's activation time

            --------------------------------------------------------

            else

              if objb.last and objb.last >= obja.act then

                oleft = oleft - 1

                objb.skip = true

              end

            end

          end

          --------------------------------------------------------

          if oleft == 0 then break end

        end

      end--if first

      ------------------------------------------------------------------

    end--while

    ------------------------------------------------------------------

    -- after assigning all possible locals to one variable name, the

    -- unassigned locals/objects have the skip field reset and the table

    -- is compacted, to hopefully reduce iteration time

    ------------------------------------------------------------------

    local temp, j = {}, 1

    for i = 1, nobject do

      local obj = object[i]

      if not obj.done then

        obj.skip = false

        temp[j] = obj

        j = j + 1

      end

    end

    object = temp  -- new compacted object table

    nobject = #object  -- objects left to process

    ------------------------------------------------------------------

  end--while

  ------------------------------------------------------------------

  -- after assigning all locals with new variable names, we can

  -- patch in the new names, and reprocess to get 'after' stats

  ------------------------------------------------------------------

  for i = 1, #localinfo do  -- enumerate all locals

    local obj = localinfo[i]

    local xref = obj.xref

    if obj.newname then                 -- if got new name, patch it in

      for j = 1, obj.xcount do

        local p = xref[j]               -- xrefs indexes the token list

        seminfolist[p] = obj.newname

      end

      obj.name, obj.oldname             -- adjust names

        = obj.newname, obj.name

    else

      obj.oldname = obj.name            -- for cases like 'self'

    end

  end

  ------------------------------------------------------------------

  -- deal with statistics output

  ------------------------------------------------------------------

  if gotself then  -- add 'self' to end of list

    varlist[#varlist + 1] = "self"

  end

  local afteruniq = preprocess(localinfo)

  ------------------------------------------------------------------

end

return {optimize = optimize}