<commit_before>-- Lua module to preprocess and parse C declarations.
-- (<NAME>, 2015)
--
-- Copyright (c) 2015-present, Facebook, Inc.
-- All rights reserved.
--
-- This source code is licensed under the BSD-style license found in
-- the LICENSE file in the root directory of this source tree. An
-- additional grant of patent rights can be found in the PATENTS file
-- in the same directory.



-- standard libs
local string = require 'string'
local coroutine = require 'coroutine'
local table = require 'table'
local io = require 'io'

-- Lua 5.1 to 5.3 compatibility
local unpack = unpack or table.unpack

-- Debugging
local DEBUG = true
if DEBUG then pcall(require,'strict') end

-- luacheck: globals cparser
-- luacheck: ignore 43 4/ti 4/li
-- luacheck: ignore 212/.*_
-- luacheck: ignore 211/is[A-Z].* 211/Type
-- luacheck: ignore 542


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- ALL UGLY HACKS SHOULD BE HERE


-- Sometimes we cannot find system include files but need to know at
-- least things about them. For instance, certain system include files
-- define alternate forms for keywords. 

local knownIncludeQuirks = {}

knownIncludeQuirks["<complex.h>"] = { -- c99
   "#ifndef complex", "# define complex _Complex", "#endif"
}

knownIncludeQuirks["<stdbool.h>"] = { -- c99
   "#ifndef bool", "# define bool _Bool", "#endif"
}

knownIncludeQuirks["<stdalign.h>"] = { -- c11
   "#ifndef alignof", "# define alignof _Alignof", "#endif",
   "#ifndef alignas", "# define alignas _Alignas", "#endif"
}

knownIncludeQuirks["<stdnoreturn.h>"] = { -- c11
   "#ifndef noreturn", "# define noreturn _Noreturn", "#endif"
}

knownIncludeQuirks["<threads.h>"] = { -- c11
   "#ifndef thread_local", "# define thread_local _Thread_local", "#endif"
}

knownIncludeQuirks["<iso646.h>"] = { -- c++
   "#define and &&", "#define and_eq &=", "#define bitand &", "#define bitor |",
   "#define compl ~", "#define not !", "#define not_eq !=", "#define or ||",
   "#define or_eq |=", "#define xor ^", "#define xor_eq ^="
}


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- TAGGED TABLES


-- Utilities to produce and print tagged tables.
-- The tag name is simply the contents of table key <tag>.
-- Function <newTag> returns a node constructor
--
-- Example:
--
-- > Foo = newTag('Foo')
-- > Bar = newTag('Bar')
--
-- > print( Foo{const=true,next=Bar{name="Hello"}} )
-- Foo{next=Bar{name="Hello"},const=true}
--
-- > print( Bar{name="hi!", Foo{1}, Foo{2}, Foo{3}} )
-- Bar{Foo{1},Foo{2},Foo{3},name="hi!"}

local function newTag(tag)
   -- the printing function
   local function tostr(self)
      local function str(x)
	 if type(x)=='string' then
	    return string.format("%q",x):gsub("\\\n","\\n")
	 elseif type(x)=='table' and not getmetatable(x) then
	    return "{..}"
	 else
	    return tostring(x)
	 end
      end
      local p = string.format("%s{", self.tag or "Node")
      local s = {}
      local seqlen = 0
      for i=1,#self do
	 if self[i] then seqlen=i else break end end
      for i=1,seqlen do
	 s[1+#s] = str(self[i]) end
      for k,v in pairs(self) do
	 if type(k) == 'number' then
	    if k<1 or k>seqlen then
	       s[1+#s] = string.format("[%s]=%s",k,str(v)) end
	 elseif type(k) ~= 'string' then
	    s.extra = true
	 elseif k:find("^_") and type(v)=='table' then
	    s[1+#s] = string.format("%s={..}",k) -- hidden
	 elseif k ~= 'tag' then
	    s[1+#s] = string.format("%s=%s",k,str(v)) end
      end
      if s.extra then s[1+#s] = "..." end
      return p .. table.concat(s,',') .. '}'
   end
   -- the constructor
   return function(t) -- must be followed by a table constructor
      t = t or {}
      assert(type(t)=='table')
      setmetatable(t, { __tostring=tostr } )
      t.tag = tag
      return t
   end
end

-- hack to print any table: print(Node(nn))
local Node = newTag(nil)   -- luacheck: ignore 211

---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- UTILITIES


-- Many functions below have an optional argument 'options' which is
-- simply an array of compiler-like options that are specified in the
-- toplevel call and passed to nearly all functions. Because it
-- provides a good communication channel across the code components,
-- many named fields are also used for multiple purposes. The
-- following function is called at the beginning of the user facing
-- functions to make a copy of the user provided option array and
-- setup some of these fields.

local function copyOptions(options)
   options = options or {}
   assert(type(options)=='table')
   local noptions = {}
   -- copy options
   for k,v in ipairs(options) do noptions[k]=v end
   -- copy user modifiable named fields
   noptions.sizeof = options.sizeof     -- not used yet
   noptions.alignof = options.alignof   -- not used yet
   -- create reversed hash
   noptions.hash = {}
   for i,v in ipairs(options) do
      noptions.hash[v] = i
   end
   -- compute dialect flags
   local dialect = 'gnu99'
   for _,v in ipairs(options) do
      if v:find("^%-std=%s*[^%s]") then
	 dialect = v:match("^%-std=%s*(.-)%s*$")
      end
   end
   noptions.dialect = dialect
   noptions.dialectGnu = dialect:find("^gnu")
   noptions.dialect99 = dialect:find("9[9x]$")
   noptions.dialect11 = dialect:find("1[1x]$")
   noptions.dialectAnsi = not noptions.dialectGnu
   noptions.dialectAnsi = noptions.dialectAnsi and not noptions.dialect99
   noptions.dialectAnsi = noptions.dialectAnsi and not noptions.dialect11
   -- return
   return noptions
end


-- This function tests whether a particular option has been given.

local function hasOption(options, opt)
   assert(options)
   assert(options.silent or options.hash)
   return options.hash and options.hash[opt]
end


-- Generic functions for error messages

local function xmessage(err, options, lineno, message, ...)
   local msg = string.format("cparser: (%s) ",lineno)
   msg = msg .. string.format(message,...)
   if options.silent then
      if err == 'error' then error(msg, 0) end
   else
      if err == 'warning' and hasOption(options, "-Werror") then err = 'error' end
      if err == 'error' or not hasOption(options, "-w") then print(msg) end
      if err == 'error' then error("cparser: aborted",0) end
   end
end

local function xwarning(options, lineno, message, ...)
   xmessage('warning', options, lineno, message, ...)
end

local function xerror(options, lineno, message, ...)
   xmessage('error', options, lineno, message, ...)
end

local function xassert(cond, ...)
   if not cond then xerror(...) end
end

local function xdebug(lineno,message,...)
   local msg = string.format("\t\t[%s] ", lineno)
   msg = msg .. string.format(message,...)
   print(msg)
end


-- Nil-safe max

local function max(a,b)
   a = a or b
   b = b or a
   return a > b and a or b
end


-- Deep table comparison
-- (not very efficient, no loop detection)

local function tableCompare(a,b)
   if a == b then
      return true
   elseif type(a) == 'table' and type(b) == 'table' then
      for k,v in pairs(a) do
	 if not tableCompare(v,b[k]) then return false end
      end
      for k,v in pairs(b) do
	 if not tableCompare(a[k],v) then return false end
      end
      return true
   else
      return false
   end
end


-- Concatenate two possibly null arrays

local function tableAppend(a1, a2)
   if not a1 then
      return a2
   elseif not a2 then
      return a1
   else
      local a = {}
      for _,v in ipairs(a1) do a[1+#a] = v end
      for _,v in ipairs(a2) do a[1+#a] = v end
      return a
   end
end


-- Evaluate a lua expression, return nil on error.

local function evalLuaExpression(s)
   assert(type(s)=='string')
   local f = load(string.gmatch(s,".*"))
   local function r(status,...) 
      if status then return ... end end
   return r(pcall(f or error))
end


-- Bitwise manipulations
-- try lua53 operators otherwise revert to iterative version

local bit = evalLuaExpression [==[
   local bit = {} 
   function bit.bnot(a) return ~a end
   function bit.bor(a,b) return a | b end
   function bit.band(a,b) return a & b end
   function bit.bxor(a,b) return a ~ b end
   function bit.lshift(a,b) return a < 0 and b < 0 and ~((~a) << b) or a << b end
   return bit 
]==]

if not bit then 
   local function bor(a,b)
      local r, c, d = 0, 1, -1
      while a > 0 or b > 0 or a < -1 or b < -1 do
	 if a % 2 > 0 or b % 2 > 0 then r = r + c end 
	 a, b, c, d = math.floor(a / 2), math.floor(b / 2), c * 2, d * 2 end
      if a < 0 or b < 0 then r = r + d end
      return r end
   bit = {}
   function bit.bnot(a) return -1-a end
   function bit.bor(a,b) return bor(a,b) end
   function bit.band(a,b) return -1-bor(-1-a,-1-b) end
   function bit.bxor(a,b) return bor(-1-bor(a,-1-b),-1-bor(-1-a,b)) end
   function bit.lshift(a,b) return math.floor(a * 2 ^ b) end
end


-- Coroutine helpers.
-- This code uses many coroutines that yield lines or tokens.
-- All functions that can yield take an options table as first argument.


-- Wrap a coroutine f into an iterator
-- The options and all the extra arguments are passed
-- to the coroutine when it starts. Together with the
-- above calling convention, this lets us specify
-- coroutine pipelines (see example in function "cpp".)

local function wrap(options, f, ...)
   local function g(...) coroutine.yield(nil) f(...) end
   local c = coroutine.create(g)
   coroutine.resume(c, options, ...)
   local function r(s,...)
      if not s then local m = ... ; error(m, 0) end
      return ...
   end
   return function()
      if coroutine.status(c) ~= 'dead' then
	 return r(coroutine.resume(c))
      end
   end
end


-- Collect coroutine outputs into an array
-- The options and the extra arguments are passed to the coroutine.

local function callAndCollect(options, f, ...) -- Bell Labs nostalgia
   local collect = {}
   for s in wrap(options, f, ...) do
      collect[1+#collect] = s
   end
   return collect
end


-- Yields all outputs from iterator iter.
-- Argument options is ignored.

local function yieldFromIterator(options_, iter)
   local function yes(v,...) coroutine.yield(v,...) return v end
   while yes(iter()) do end
end


-- Yields all values from array <arr>.
-- This function unpacks table values and yields the result.
-- For all other values, this function yields the value plut its extra arguments.
-- Argument options is ignored.

local function yieldFromArray(options_, arr, ...)
   -- luacheck: ignore 212/options
   for _,v in ipairs(arr) do
      if type(v) == 'table' then
	 coroutine.yield(unpack(v))
      else
	 coroutine.yield(v, ...)
      end
   end
end





---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- INITIAL PREPROCESSING 



-- A routine that pulls lines from a line iterator
-- and yields them together with a location
-- composed of the optional prefix, a colon, and a line number.
-- Argument options is ignored.
-- Lua provides good line iterators such as:
--   io.lines(filename) filedesc:lines()  str:gmatch("[^\n]+")

local function yieldLines(options_,lineIterator,prefix)
   prefix = prefix or ""
   assert(type(prefix)=='string')
   local n = 0
   for s in lineIterator do
      n = n + 1
      coroutine.yield(s, string.format("%s:%d", prefix, n))
   end
end


-- A routine that obtain lines from coroutine <lines>,
-- joins lines terminated by a backslash, and yield the
-- resulting lines. The coroutine is initialized with
-- argument <options> and all extra arguments.
-- Reference: https://gcc.gnu.org/onlinedocs/cpp/Initial-processing.html (3)

local function joinLines(options, lines, ...)
   local li = wrap(options, lines, ...)
   for s, n in li do
      while type(s) == 'string' and s:find("\\%s*$") do
	 local t = li() or ""
	 s = s:gsub("\\%s*$", "") .. t
      end
      coroutine.yield(s, n)
   end
end


-- A routine that obtain lines from coroutine <lines>, eliminate the
-- comments and yields the resulting lines.  The coroutine is
-- initialized with argument <options> and all extra arguments.
-- Reference: https://gcc.gnu.org/onlinedocs/cpp/Initial-processing.html (4)

local function eliminateComments(options, lines, ...)
   local lineIterator = wrap(options, lines, ...)
   local inComment = false
   local s,n = lineIterator()
   while type(s) == 'string' do
      while inComment do
	 local p = s:find("%*/")
	 if p ~= nil then
	    inComment = false
	    s = s:sub(p+2)
	 else
	    local m = n
	    s, n = lineIterator()
	    xassert(s ~= nil, options, m, "Unterminated comment")
	 end
      end
      local inString = false
      local q = s:find("[\'\"\\/]", 1)
      while q ~= nil do
	 if hasOption(options,"-d:comments") then 
	    xdebug(n, "comment: [%s][%s] %s",s:sub(1,q-1),s:sub(q),inString)
	 end
	 local c = s:byte(q)
	 if inString then
	    if c == 92 then -- \
	       q = q + 1
	    elseif c == inString then
	       inString = false
	    end
	 else
	    if c == 34 or c == 39 then -- " or '
	       inString = c
	    elseif c == 47 and s:byte(q+1) == 47 then -- "//"
	       s = s:sub(1,q-1)
	    elseif c == 47 and s:byte(q+1) == 42 then -- "/*"
	       local p = s:find("%*/",q+2)
	       if p ~= nil then
		  s = s:sub(1,q-1) .. " " .. s:sub(p+2)
	       else
		  s = s:sub(1,q-1)
		  inComment = true
	       end
	    end
	 end
	 q = s:find("[\'\"\\/]", q+1)
      end
      coroutine.yield(s, n)
      s, n = lineIterator()
   end
end



---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- TOKENIZER



local keywordTable = {
   ------ Standard keywords
   "auto", "break", "case", "char", "const", "continue", "default", "do",
   "double", "else", "enum", "extern", "float", "for", "goto", "if", "int",
   "long", "register", "return", "short", "signed", "sizeof", "static", "struct",
   "switch", "typedef", "union", "unsigned", "void", "volatile", "while",
   ------ Nonstandard or dialect specific keywords do not belong here
   ------ because the main function of this table is to say which
   ------ identifiers cannot be variable names.
}
   
local punctuatorTable = {
   "+", "-", "*", "/", "%", "&", "|", "^", ">>", "<<", "~",
   "=", "+=", "-=", "*=", "/=", "%=", "&=", "|=", "^=", ">>=", "<<=",
   "(", ")", "[", "]", "{", "}", "++", "--",
   "==", "!=", ">=", "<=", ">", "<", "&&", "||", "!",
   ".", "->", "*", "&", "?", ":", "::", "->*", ".*", ";", ",",
   "#", "##", "..." -- preprocessor stuff
}

local keywordHash = {}
for _,v in ipairs(keywordTable) do
   keywordHash[v] = true
end

local punctuatorHash = {}
for _,v in ipairs(punctuatorTable) do
   local l = v:len()
   local b = v:byte()
   punctuatorHash[v] = true
   punctuatorHash[b] = max(l,punctuatorHash[b])
end


-- The following functions test the types of the tokens returned by the tokenizer.
-- They should not be applied to arbitrary strings

local function isSpace(tok)
   return tok and tok:find("^%s") ~= nil end
local function isNewline(tok) -- Subtype of space
   return tok and tok:find("^\n") ~= nil end 
local function isNumber(tok)
   return tok and tok:find("^[.0-9]") ~= nil end
local function isString(tok)
   if tok then return tok:find("^[\'\"]") ~= nil
      or tok:find("^<") and tok:find(">$") end end
local function isPunctuator(tok)
   return tok and punctuatorHash[tok] ~= nil end
local function isIdentifier(tok)
   return tok and tok:find("^[A-Za-z_$]") ~= nil end
local function isKeyword(tok) -- Subtype of identifier
   return tok and keywordHash[tok] ~= nil end
local function isName(tok) -- Subtype of identifier
   return tok and isIdentifier(tok) and not keywordHash[tok] end


-- The tokenizeLine() function takes a line, splits it into tokens,
-- and yields tokens and locations. The number tokens are the weird
-- preprocessor numbers defined by ansi c. The string tokens include
-- character constants and angle-bracket delimited strings occuring
-- after an include directive. Every line begins with a newline
-- token giving the proper indentation. All subsequent spaces
-- are reduced to a single space character.

local function tokenizeLine(options, s, n, notNewline)
   -- little optimization for multiline macros
   -- s may be an array of precomputed tokens
   if type(s) == 'table' then
      return yieldFromArray(options, s, n)
   end
   -- normal operation
   assert(type(s) == 'string')
   local p = s:find("[^%s]")
   -- produce a newline token
   if p and not notNewline then
      local r = '\n' .. s:sub(1,p-1)
      coroutine.yield(r, n)
   end
   -- produce one token
   local function token()
      local b, l, r
      if hasOption(options, "-d:tokenize") then
	 xdebug(n, "[%s][%s]",s:sub(1,p-1),s:sub(p))
      end
      -- space
      l = s:find("[^%s]", p)
      if l == nil then
	 return nil
      elseif l > p then
	 p = l
	 return " ", n
      end
      -- identifier
      r = s:match("^[a-zA-Z_$][a-zA-Z0-9_$]*", p)
      if r ~= nil then
	 p = p + r:len()
	 return r, n
      end
      -- preprocessor numbers
      r = s:match("^%.?[0-9][0-9a-zA-Z._]*", p)
      if r ~= nil then
	 l = r:len()
	 while r:find("[eEpP]$") and s:find("^[-+]", p+l) do
	    r = r .. s:match("^[-+][0-9a-zA-Z._]*", p+l)
	    l = r:len()
	 end
	 p = p + l
	 return r, n
      end
      -- angle-delimited strings in include directives
      b = s:byte(p)
      if b == 60 and s:find("^%s*#%s*include") then
	 r = s:match("^<[^>]+>", p)
	 if r ~= nil then
	    p = p + r:len()
	    return r, n
	 end
      end
      -- punctuator
      l = punctuatorHash[b]
      if l ~= nil then
	 while l > 0 do
	    r = s:sub(p,p+l-1)
	    if punctuatorHash[r] then
	       p = p + l
	       return r, n
	    end
	    l = l - 1
	 end
      end
      -- string
      if b == 34 or b == 39 then -- quotes
	 local q = p
	 repeat
	    q = s:find("[\'\"\\]", q + 1)
	    l = s:byte(q)
	    xassert(q ~= nil, options, n, "Unterminated string or character constant")
	    if l == 92 then
	       q = q + 1
	    end
	 until l == b
	 r = s:sub(p,q)
	 p = q + 1
	 return r, n
      end
      -- error
      xerror(options, n,"Unrecognized character (%s)", s:sub(p))
   end
   -- loop
   if p then
      for tok,tokn in token do
	 coroutine.yield(tok, tokn)
      end
   end
end


-- Obtain lines from coroutine <lines>,
-- and yields their tokens. The coroutine is initialized with
-- argument <options> and all extra arguments.

local function tokenize(options, lines, ...)
   for s,n in wrap(options, lines, ...) do
      tokenizeLine(options, s, n)
   end
end


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- PREPROCESSING 


-- Preprocessing is performed by two coroutines. The first one
-- processes all the preprocessor directives and yields the remaining
-- lines. The second one processes tokens from the remaining lines and
-- perform macro expansions. Both take a table of macro definitions as
-- argument. The first one writes into the table and the second one
-- reads from it.

-- Each macro definition is simply an array of tokens.
-- If the macro takes arguments (function-like macro),
-- the table also contains an entry 'args' with a list
-- of argument names. Finally the table may contain
-- a function which is called at macro-expansion time.
-- This provides for complicated situations.

-- forward declarations
local function expandMacros() end
local function processDirectives() end


-- Starting with the second coroutine which takes a token producing
-- coroutine and yields the preprocessed tokens. Argument macros is
-- the macro definition table.

expandMacros = function(options, macros, tokens, ...)
   local ti = wrap(options, tokens, ...)
   local tok, n = ti()
   -- redefine ti() to ensure tok,n remain up-to-date
   local ti = function() tok,n=ti() return tok,n end
   -- create a macro table that inherits <macros> but hides <symbol>
   local function hideMacro(macros,symbol)
      local nmacros = {}
      setmetatable(nmacros, {__index=macros})
      if macros[symbol] and macros[symbol].recursive then
	 -- limit number of recursive macro invocations
	 if not options.maxrecursion then
	    for _,v in ipairs(options) do
	       if type(v)=='string' and v:find("^%-Zmaxrecursion=") then
		  options.maxrecursion = tonumber(v:match("-Zmaxrecursion=%s*(%d+)%s*$"))
	       end
	    end
	 end
	 -- we use macros[0] to keep track of the recursion count.
	 -- this is not going to collide with any macro symbol because 0 is a number.
	 local maxrecursion = options.maxrecursion or 100
	 nmacros[0] = 1 + (macros[0] or 0) 
	 xassert(nmacros[0] < maxrecursion, options, n,
	 	 "more than %d recursive macro invocations", maxrecursion)
      else
	 -- standard recursion prevention feature
	 nmacros[symbol] = false
      end
      return nmacros
   end
   -- collect one macro arguments into an array
   -- stop when reaching a closing parenthesis or a comma 
   local function collectArgument(ti, varargs)
      local count = 0
      local tokens = {}
      ti()
      while isSpace(tok) do
	 tok = ti()
      end
      while tok do
	 if tok == ')' and count == 0 then
	    break
	 elseif tok == ')' then
	    count = count - 1
	 elseif tok == '(' then
	    count = count + 1
	 elseif tok == ',' and count == 0 and not varargs then
	    break
	 end
	 if isSpace(tok) then tok = " " end
	 tokens[1+#tokens] = tok
	 tok = ti()
      end
      if #tokens > 0 and isSpace(tokens[#tokens]) then
	 tokens[#tokens] = nil
      end
      return tokens
   end
   -- collects all macro arguments
   local function collectArguments(ti,args,ntok,nn)
      local nargs = { [0]={} }
      for _,name in ipairs(args) do
	 if tok == ')' and name == "__VA_ARGS__" then
	    nargs[0][name] = { negComma=true }
	    nargs[name] = { negComma=true }
	 else
	    xassert(tok=='(' or tok==',', options, nn, "not enough arguments for macro '%s'", ntok)
	    local arg = collectArgument(ti, name == "__VA_ARGS__")
	    nargs[0][name] = arg
	    nargs[name] = callAndCollect(options, expandMacros, macros, yieldFromArray, arg, nn)
	 end
      end
      xassert(tok, options, nn, "unterminated arguments for macro '%s'", tok)
      xassert(tok==')', options, nn, "too many arguments for macro '%s'", tok)
      return nargs
   end
   -- coroutine that substitute the macro arguments
   -- and stringification and concatenation are handled here
   local function substituteArguments(options, def, nargs, n, inDirective)
      local uargs = nargs[0] -- unprocessed values
      if inDirective then nargs = uargs end  -- always use unprocessed in directives
      -- prepare loop
      local i,j,k = 1,1,1
      while def[i] do
	 if isSpace(def[i]) then
	    -- copy spaces
	    coroutine.yield(def[i], n)
	 else
	    -- positions j and k on next non-space tokens
	    local function updateJandK()
	       if j <= i then j=i
		  repeat j=j+1 until def[j] == nil or not isSpace(def[j]) end
	       if k <= j then k=j
		  repeat k=k+1 until def[k] == nil or not isSpace(def[k]) end
	    end
	    updateJandK()
	    -- alternatives
	    if def[i]=='#' and def[j] and nargs[def[j]] then
	       -- stringification
	       local v = def[j]
	       local s = string.format("%q", table.concat(uargs[v])):gsub("\\\n","\\n")
	       coroutine.yield(s, n)
	       i = j
	    elseif def[j]=='##' and def[k] and not inDirective then
	       -- concatenation
	       local u = {}
	       local function addToU(s)
		  if nargs[s] then for _,v in ipairs(uargs[s]) do u[1+#u] = v end
		  else u[1+#u]=s end
	       end
	       addToU(def[i])
	       while def[j] == '##' and def[k] do
		  addToU(def[k])
		  i = k
		  updateJandK()
	       end
	       tokenizeLine(options, table.concat(u), n, true)
	    elseif def[i]==',' and def[j]=='__VA_ARGS__' and def[k]==')'
	       and nargs[def[j]].negComma then
	       -- negative comma
	       i = j
	    elseif nargs[def[i]] then
	       -- substitution
	       yieldFromArray(options, nargs[def[i]], n)
	    else
	       -- copy
	       coroutine.yield(def[i], n)
	    end
	 end
	 i = i + 1
      end
   end
   -- main loop
   local newline, directive = true, false
   while tok ~= nil do
      -- detects Zpassed directives
      if newline and tok == '#' then
	 newline, directive = false, true
      elseif not isSpace(tok) then
	 newline = false
      elseif isNewline(tok) then
	 newline, directive = true, false
      end
      -- process code
      local def = macros[tok]
      if not def or directive then
	 -- not a macro
	 coroutine.yield(tok, n)
      elseif type(def) == 'function' then
	 -- magic macro
	 def(ti,tok,n)
      elseif def.args == nil then
	 -- object-like macro
	 local nmacros = hideMacro(macros,tok)
	 expandMacros(options, nmacros, yieldFromArray, def, n)
      elseif def.lines == nil then
	 -- single-line function-like macro
	 local ntok,nn = tok,n
	 repeat ti() until not isSpace(tok)
	 if (tok ~= '(') then
	    coroutine.yield(ntok, nn)
	    coroutine.yield(tok, nn)
	 else
	    local nmacros = hideMacro(macros,ntok)
	    local nargs = collectArguments(ti,def.args,ntok,nn)
	    expandMacros(options, nmacros, substituteArguments, def, nargs, nn)
	 end
      else
	 -- multi-line function-like macro
	 local ntok,nn = tok,n
	 repeat ti() until not isSpace(tok)
	 if (tok ~= '(') then
	    coroutine.yield(ntok, nn)
	    coroutine.yield(tok, nn)
	 else
	    local lines = def.lines
	    local nargs = collectArguments(ti,def.args,ntok,nn)
	    local nmacros = hideMacro(macros,ntok)
	    -- a coroutine that yields the macro definition
	    local function yieldMacroLines()
	       local count = 0
	       for i=1,#lines,2 do
		  local ls,ln = lines[i], lines[i+1]
 		  -- are we possibly in a cpp directive
		  local dir = false
		  if ls[2] and ls[2]:find('^#') then
		     dir = isIdentifier(ls[3]) and ls[3] or ls[4]
		  end
		  if dir and nargs[dir] then
		     dir = false      -- leading stringification
		  elseif dir == 'defmacro' then
		     count = count + 1  -- entering a multiline macto
		  elseif dir == 'endmacro' then
		     count = count - 1  -- leaving a multiline macro
		  end
		  dir = dir or count > 0
		  -- substitute
		  --print(string.format("<<< [%s]",table.concat(ls,"|",2)))
		  ls = callAndCollect(options,substituteArguments,ls,nargs,ln,dir)
		  --print(string.format(">>> [%s]",table.concat(ls,"|",2)))
		  -- compute lines (optimize speed by passing body lines as tokens)
		  if ls[2] and ls[2]:find("^#") then -- but not directives
		     ls = ls[1]:sub(2) .. table.concat(ls, nil, 2)
		  end
		  coroutine.yield(ls,ln)
	       end
	    end
	    -- reenter the preprocessing subroutines
	    expandMacros(options, nmacros,
			 tokenize, processDirectives, nmacros,
			 yieldMacroLines)
	 end
      end
      ti()
   end
end


-- Processing conditional directive requires evaluating conditions
-- This function takes an iterator on preprocessed expression tokens
-- and computes the value. This does not handle defined(X) expressions.
-- Optional argument resolver is a function that takes an indentifer
-- name and returns a value. Otherwise zero is assumed

local function evaluateCppExpression(options, tokenIterator, n, resolver)
   -- redefine token iterator to skip spaces and update tok
   local tok
   local function ti()
      repeat tok = tokenIterator()
      until not isSpace(tok) return tok
   end
   -- operator tables
   local unaryOps = {
      ["!"] = function(v) return v == 0 and 1 or 0 end,
      ["~"] = function(v) return bit.bnot(v) end,
      ["+"] = function(v) return v end,
      ["-"] = function(v) return -v end
   }
   local binaryOps = {
      ["*"] = function(a,b) return a * b end,
      ["/"] = function(a,b) xassert(b~=0,options,n,"division by zero"); return math.floor(a / b) end,
      ["%"] = function(a,b) xassert(b~=0,options,n,"division by zero"); return a % b end,
      ["+"] = function(a,b) return a + b end,
      ["-"] = function(a,b) return a - b end,
      [">>"] = function(a,b) return bit.lshift(a, -b) end,
      ["<<"] = function(a,b) return bit.lshift(a, b) end,
      [">="] = function(a,b) return a >= b and 1 or 0 end,
      ["<="] = function(a,b) return a <= b and 1 or 0 end,
      [">"] = function(a,b) return a > b and 1 or 0 end,
      ["<"] = function(a,b) return a < b and 1 or 0 end,
      ["=="] = function(a,b) return a == b and 1 or 0 end,
      ["!="] = function(a,b) return a ~= b and 1 or 0 end,	 
      ["&"] = function(a,b) return bit.band(a,b) end,
      ["^"] = function(a,b) return bit.bxor(a,b) end,
      ["|"] = function(a,b) return bit.bor(a,b) end,
      ["&&"] = function(a,b) return (a ~= 0 and b ~= 0) and 1 or 0 end,
      ["||"] = function(a,b) return (a ~= 0 or b ~= 0) and 1 or 0 end,
   }
   local binaryPrec = {
      ["*"] = 1, ["/"] = 1, ["%"] = 1,
      ["+"] = 2, ["-"] = 2,
      [">>"] = 3, ["<<"] = 3,
      [">="] = 4, ["<="] = 4, ["<"] = 4, [">"] = 4,
      ["=="] = 5, ["!="] = 5,
      ["&"] = 6, ["^"] = 7, ["|"] = 8,
      ["&&"] = 9, ["||"] = 10
   }
   -- forward
   local function evaluate() end
   -- unary operations
   local function evalUnary()
      if unaryOps[tok] then
	 local op = unaryOps[tok]
	 ti(); return op(evalUnary())
      elseif tok == '(' then
	 ti(); local v = evaluate()
	 xassert(tok == ')', options, n, "missing closing parenthesis")
	 ti(); return v
      elseif tok == 'defined' then -- magic macro should have removed this
	 xerror(options, n, "syntax error after <defined>")
      elseif isIdentifier(tok) then
         local v = type(resolver) == 'function' and resolver(tok,ti)
	 ti(); return v or 0
      elseif isNumber(tok) then
	 local v = tok:gsub("[ULul]+$","")
	 if v:find("^0[0-7]+$") then
	    v = tonumber(v,8) -- octal
	 elseif v:find("^0[bB][01]+") then
	    v = tonumber(v:sub(3),2) -- binary
	 else
	    v = tonumber(v) -- lua does the rest
	 end
	 xassert(v and v == math.floor(v), options, n, "syntax error (invalid integer '%s')", tok)
	 ti(); return v
      elseif isString(tok) then
	 local v = '""'
	 if tok:find("^'") then -- interpret character constant as number
	    v = evalLuaExpression(string.format("return string.byte(%s)", tok))
	    xassert(type(v)=='number', options, n, "syntax error (invalid value '%s')", tok)
	    ti()
	 else
	    while isString(tok) do
	       xassert(tok:find('^"'), options, n, "syntax error (invalid value '%s')", tok)
	       v = v:gsub('"$','') .. tok:gsub('^"','')
	       ti()
	    end
	 end
	 return v
      end
      xerror(options, n, "syntax error (invalid value '%s')", tok)
   end
   -- binary operations
   local function evalBinary(p)
      if p == 0 then
	 return evalUnary()
      else
	 local val = evalBinary(p-1)
	 while binaryPrec[tok] == p do
	    local op = binaryOps[tok]  ti()
	    local oval = evalBinary(p-1)
	    xassert(p==4 or p==5 or type(val)=='number', options, n,
		    "expression uses arithmetic operators on strings")
	    xassert(type(val) == type(oval), options, n,
		    "expression compares numbers and strings")
	    val = op(val,oval)
	 end
	 return val
      end
   end
   -- eval ternary conditonal
   local function evalTernary()
      local c = evalBinary(10)
      if tok ~= '?' then return c end
      ti() local v1 = evalBinary(10)
      xassert(tok == ':', options, n, "expecting ':' after '?'")
      ti() local v2 = evalBinary(10)
      if c == 0 then return v2 else return v1 end
   end

   -- actual definition of evaluate
   evaluate = function()
      return evalTernary()
   end
   -- main function
   ti()
   xassert(tok, options, n, "constant expression expected");
   local result = evaluate()
   if hasOption(options, "-d:eval") then
      xdebug(n, "eval %s", result)
   end
   -- warn about garbage when called from cpp (but not when called with resolver)
   xassert(resolver or not tok, options, n, "garbage after conditional expression");
   return result
end


-- Now dealing with the coroutine thay processes all directives.
-- This coroutine obtains lines from coroutine <lines>,
-- processes all directives, and yields remaining lines

processDirectives = function(options, macros, lines, ...)
   local li = wrap(options, lines, ...)
   local s, n = li()
   -- redefine li to make sure vars s and n are up-to-date
   local li = function() s,n=li() return s,n end
   -- directives store their current token in these vars
   local dirtok, tok, spc
   -- forward declaration
   local processLine
   -- the captureTable mechanism communicates certain preprocessor
   -- events to the declaration parser in order to report them
   -- to the user (the parsing does not depend on this).
   -- if macros[1] is a table, the preprocessor will append
   -- records to this table for the parser to process.
   local function hasCaptureTable()
      local captable = rawget(macros,1)
      return captable and type(captable)=='table' and captable
   end
   local function addToCaptureTable(record)
      local captable = hasCaptureTable()<commit_msg>improved comments<commit_after>-- Lua module to preprocess and parse C declarations.
-- (<NAME>, 2015)
--
-- Copyright (c) 2015-present, Facebook, Inc.
-- All rights reserved.
--
-- This source code is licensed under the BSD-style license found in
-- the LICENSE file in the root directory of this source tree. An
-- additional grant of patent rights can be found in the PATENTS file
-- in the same directory.



-- standard libs
local string = require 'string'
local coroutine = require 'coroutine'
local table = require 'table'
local io = require 'io'

-- Lua 5.1 to 5.3 compatibility
local unpack = unpack or table.unpack

-- Debugging
local DEBUG = true
if DEBUG then pcall(require,'strict') end

-- luacheck: globals cparser
-- luacheck: ignore 43 4/ti 4/li
-- luacheck: ignore 212/.*_
-- luacheck: ignore 211/is[A-Z].* 211/Type
-- luacheck: ignore 542


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- ALL UGLY HACKS SHOULD BE HERE


-- Sometimes we cannot find system include files but need to know at
-- least things about them. For instance, certain system include files
-- define alternate forms for keywords. 

local knownIncludeQuirks = {}

knownIncludeQuirks["<complex.h>"] = { -- c99
   "#ifndef complex", "# define complex _Complex", "#endif"
}

knownIncludeQuirks["<stdbool.h>"] = { -- c99
   "#ifndef bool", "# define bool _Bool", "#endif"
}

knownIncludeQuirks["<stdalign.h>"] = { -- c11
   "#ifndef alignof", "# define alignof _Alignof", "#endif",
   "#ifndef alignas", "# define alignas _Alignas", "#endif"
}

knownIncludeQuirks["<stdnoreturn.h>"] = { -- c11
   "#ifndef noreturn", "# define noreturn _Noreturn", "#endif"
}

knownIncludeQuirks["<threads.h>"] = { -- c11
   "#ifndef thread_local", "# define thread_local _Thread_local", "#endif"
}

knownIncludeQuirks["<iso646.h>"] = { -- c++
   "#define and &&", "#define and_eq &=", "#define bitand &", "#define bitor |",
   "#define compl ~", "#define not !", "#define not_eq !=", "#define or ||",
   "#define or_eq |=", "#define xor ^", "#define xor_eq ^="
}


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- TAGGED TABLES


-- Utilities to produce and print tagged tables.
-- The tag name is simply the contents of table key <tag>.
-- Function <newTag> returns a node constructor
--
-- Example:
--
-- > Foo = newTag('Foo')
-- > Bar = newTag('Bar')
--
-- > print( Foo{const=true,next=Bar{name="Hello"}} )
-- Foo{next=Bar{name="Hello"},const=true}
--
-- > print( Bar{name="hi!", Foo{1}, Foo{2}, Foo{3}} )
-- Bar{Foo{1},Foo{2},Foo{3},name="hi!"}

local function newTag(tag)
   -- the printing function
   local function tostr(self)
      local function str(x)
	 if type(x)=='string' then
	    return string.format("%q",x):gsub("\\\n","\\n")
	 elseif type(x)=='table' and not getmetatable(x) then
	    return "{..}"
	 else
	    return tostring(x)
	 end
      end
      local p = string.format("%s{", self.tag or "Node")
      local s = {}
      local seqlen = 0
      for i=1,#self do
	 if self[i] then seqlen=i else break end end
      for i=1,seqlen do
	 s[1+#s] = str(self[i]) end
      for k,v in pairs(self) do
	 if type(k) == 'number' then
	    if k<1 or k>seqlen then
	       s[1+#s] = string.format("[%s]=%s",k,str(v)) end
	 elseif type(k) ~= 'string' then
	    s.extra = true
	 elseif k:find("^_") and type(v)=='table' then
	    s[1+#s] = string.format("%s={..}",k) -- hidden
	 elseif k ~= 'tag' then
	    s[1+#s] = string.format("%s=%s",k,str(v)) end
      end
      if s.extra then s[1+#s] = "..." end
      return p .. table.concat(s,',') .. '}'
   end
   -- the constructor
   return function(t) -- must be followed by a table constructor
      t = t or {}
      assert(type(t)=='table')
      setmetatable(t, { __tostring=tostr } )
      t.tag = tag
      return t
   end
end

-- hack to print any table: print(Node(nn))
local Node = newTag(nil)   -- luacheck: ignore 211

---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- UTILITIES


-- Many functions below have an optional argument 'options' which is
-- simply an array of compiler-like options that are specified in the
-- toplevel call and passed to nearly all functions. Because it
-- provides a good communication channel across the code components,
-- many named fields are also used for multiple purposes. The
-- following function is called at the beginning of the user facing
-- functions to make a copy of the user provided option array and
-- setup some of these fields.

local function copyOptions(options)
   options = options or {}
   assert(type(options)=='table')
   local noptions = {}
   -- copy options
   for k,v in ipairs(options) do noptions[k]=v end
   -- copy user modifiable named fields
   noptions.sizeof = options.sizeof     -- not used yet
   noptions.alignof = options.alignof   -- not used yet
   -- create reversed hash
   noptions.hash = {}
   for i,v in ipairs(options) do
      noptions.hash[v] = i
   end
   -- compute dialect flags
   local dialect = 'gnu99'
   for _,v in ipairs(options) do
      if v:find("^%-std=%s*[^%s]") then
	 dialect = v:match("^%-std=%s*(.-)%s*$")
      end
   end
   noptions.dialect = dialect
   noptions.dialectGnu = dialect:find("^gnu")
   noptions.dialect99 = dialect:find("9[9x]$")
   noptions.dialect11 = dialect:find("1[1x]$")
   noptions.dialectAnsi = not noptions.dialectGnu
   noptions.dialectAnsi = noptions.dialectAnsi and not noptions.dialect99
   noptions.dialectAnsi = noptions.dialectAnsi and not noptions.dialect11
   -- return
   return noptions
end


-- This function tests whether a particular option has been given.

local function hasOption(options, opt)
   assert(options)
   assert(options.silent or options.hash)
   return options.hash and options.hash[opt]
end


-- Generic functions for error messages

local function xmessage(err, options, lineno, message, ...)
   local msg = string.format("cparser: (%s) ",lineno)
   msg = msg .. string.format(message,...)
   if options.silent then
      if err == 'error' then error(msg, 0) end
   else
      if err == 'warning' and hasOption(options, "-Werror") then err = 'error' end
      if err == 'error' or not hasOption(options, "-w") then print(msg) end
      if err == 'error' then error("cparser: aborted",0) end
   end
end

local function xwarning(options, lineno, message, ...)
   xmessage('warning', options, lineno, message, ...)
end

local function xerror(options, lineno, message, ...)
   xmessage('error', options, lineno, message, ...)
end

local function xassert(cond, ...)
   if not cond then xerror(...) end
end

local function xdebug(lineno,message,...)
   local msg = string.format("\t\t[%s] ", lineno)
   msg = msg .. string.format(message,...)
   print(msg)
end


-- Nil-safe max

local function max(a,b)
   a = a or b
   b = b or a
   return a > b and a or b
end


-- Deep table comparison
-- (not very efficient, no loop detection)

local function tableCompare(a,b)
   if a == b then
      return true
   elseif type(a) == 'table' and type(b) == 'table' then
      for k,v in pairs(a) do
	 if not tableCompare(v,b[k]) then return false end
      end
      for k,v in pairs(b) do
	 if not tableCompare(a[k],v) then return false end
      end
      return true
   else
      return false
   end
end


-- Concatenate two possibly null arrays

local function tableAppend(a1, a2)
   if not a1 then
      return a2
   elseif not a2 then
      return a1
   else
      local a = {}
      for _,v in ipairs(a1) do a[1+#a] = v end
      for _,v in ipairs(a2) do a[1+#a] = v end
      return a
   end
end


-- Evaluate a lua expression, return nil on error.

local function evalLuaExpression(s)
   assert(type(s)=='string')
   local f = load(string.gmatch(s,".*"))
   local function r(status,...) 
      if status then return ... end end
   return r(pcall(f or error))
end


-- Bitwise manipulations
-- try lua53 operators otherwise revert to iterative version

local bit = evalLuaExpression [==[
   local bit = {} 
   function bit.bnot(a) return ~a end
   function bit.bor(a,b) return a | b end
   function bit.band(a,b) return a & b end
   function bit.bxor(a,b) return a ~ b end
   function bit.lshift(a,b) return a < 0 and b < 0 and ~((~a) << b) or a << b end
   return bit 
]==]

if not bit then 
   local function bor(a,b)
      local r, c, d = 0, 1, -1
      while a > 0 or b > 0 or a < -1 or b < -1 do
	 if a % 2 > 0 or b % 2 > 0 then r = r + c end 
	 a, b, c, d = math.floor(a / 2), math.floor(b / 2), c * 2, d * 2 end
      if a < 0 or b < 0 then r = r + d end
      return r end
   bit = {}
   function bit.bnot(a) return -1-a end
   function bit.bor(a,b) return bor(a,b) end
   function bit.band(a,b) return -1-bor(-1-a,-1-b) end
   function bit.bxor(a,b) return bor(-1-bor(a,-1-b),-1-bor(-1-a,b)) end
   function bit.lshift(a,b) return math.floor(a * 2 ^ b) end
end


-- Coroutine helpers.
-- This code uses many coroutines that yield lines or tokens.
-- All functions that can yield take an options table as first argument.


-- Wrap a coroutine f into an iterator
-- The options and all the extra arguments are passed
-- to the coroutine when it starts. Together with the
-- above calling convention, this lets us specify
-- coroutine pipelines (see example in function "cpp".)

local function wrap(options, f, ...)
   local function g(...) coroutine.yield(nil) f(...) end
   local c = coroutine.create(g)
   coroutine.resume(c, options, ...)
   local function r(s,...)
      if not s then local m = ... ; error(m, 0) end
      return ...
   end
   return function()
      if coroutine.status(c) ~= 'dead' then
	 return r(coroutine.resume(c))
      end
   end
end


-- Collect coroutine outputs into an array
-- The options and the extra arguments are passed to the coroutine.

local function callAndCollect(options, f, ...) -- Bell Labs nostalgia
   local collect = {}
   for s in wrap(options, f, ...) do
      collect[1+#collect] = s
   end
   return collect
end


-- Yields all outputs from iterator iter.
-- Argument options is ignored.

local function yieldFromIterator(options_, iter)
   local function yes(v,...) coroutine.yield(v,...) return v end
   while yes(iter()) do end
end


-- Yields all values from array <arr>.
-- This function unpacks table values and yields the result.
-- For all other values, this function yields the value plut its extra arguments.
-- Argument options is ignored.

local function yieldFromArray(options_, arr, ...)
   -- luacheck: ignore 212/options
   for _,v in ipairs(arr) do
      if type(v) == 'table' then
	 coroutine.yield(unpack(v))
      else
	 coroutine.yield(v, ...)
      end
   end
end





---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- INITIAL PREPROCESSING 



-- A routine that pulls lines from a line iterator
-- and yields them together with a location
-- composed of the optional prefix, a colon, and a line number.
-- Argument options is ignored.
-- Lua provides good line iterators such as:
--   io.lines(filename) filedesc:lines()  str:gmatch("[^\n]+")

local function yieldLines(options_,lineIterator,prefix)
   prefix = prefix or ""
   assert(type(prefix)=='string')
   local n = 0
   for s in lineIterator do
      n = n + 1
      coroutine.yield(s, string.format("%s:%d", prefix, n))
   end
end


-- A routine that obtains lines from coroutine <lines>,
-- joins lines terminated by a backslash, and yield the
-- resulting lines. The coroutine is initialized with
-- argument <options> and all extra arguments.
-- Reference: https://gcc.gnu.org/onlinedocs/cpp/Initial-processing.html (3)

local function joinLines(options, lines, ...)
   local li = wrap(options, lines, ...)
   for s, n in li do
      while type(s) == 'string' and s:find("\\%s*$") do
	 local t = li() or ""
	 s = s:gsub("\\%s*$", "") .. t
      end
      coroutine.yield(s, n)
   end
end


-- A routine that obtain lines from coroutine <lines>, eliminate the
-- comments and yields the resulting lines.  The coroutine is
-- initialized with argument <options> and all extra arguments.
-- Reference: https://gcc.gnu.org/onlinedocs/cpp/Initial-processing.html (4)

local function eliminateComments(options, lines, ...)
   local lineIterator = wrap(options, lines, ...)
   local inComment = false
   local s,n = lineIterator()
   while type(s) == 'string' do
      while inComment do
	 local p = s:find("%*/")
	 if p ~= nil then
	    inComment = false
	    s = s:sub(p+2)
	 else
	    local m = n
	    s, n = lineIterator()
	    xassert(s ~= nil, options, m, "Unterminated comment")
	 end
      end
      local inString = false
      local q = s:find("[\'\"\\/]", 1)
      while q ~= nil do
	 if hasOption(options,"-d:comments") then 
	    xdebug(n, "comment: [%s][%s] %s",s:sub(1,q-1),s:sub(q),inString)
	 end
	 local c = s:byte(q)
	 if inString then
	    if c == 92 then -- \
	       q = q + 1
	    elseif c == inString then
	       inString = false
	    end
	 else
	    if c == 34 or c == 39 then -- " or '
	       inString = c
	    elseif c == 47 and s:byte(q+1) == 47 then -- "//"
	       s = s:sub(1,q-1)
	    elseif c == 47 and s:byte(q+1) == 42 then -- "/*"
	       local p = s:find("%*/",q+2)
	       if p ~= nil then
		  s = s:sub(1,q-1) .. " " .. s:sub(p+2)
	       else
		  s = s:sub(1,q-1)
		  inComment = true
	       end
	    end
	 end
	 q = s:find("[\'\"\\/]", q+1)
      end
      coroutine.yield(s, n)
      s, n = lineIterator()
   end
end



---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- TOKENIZER



local keywordTable = {
   ------ Standard keywords
   "auto", "break", "case", "char", "const", "continue", "default", "do",
   "double", "else", "enum", "extern", "float", "for", "goto", "if", "int",
   "long", "register", "return", "short", "signed", "sizeof", "static", "struct",
   "switch", "typedef", "union", "unsigned", "void", "volatile", "while",
   ------ Nonstandard or dialect specific keywords do not belong here
   ------ because the main function of this table is to say which
   ------ identifiers cannot be variable names.
}
   
local punctuatorTable = {
   "+", "-", "*", "/", "%", "&", "|", "^", ">>", "<<", "~",
   "=", "+=", "-=", "*=", "/=", "%=", "&=", "|=", "^=", ">>=", "<<=",
   "(", ")", "[", "]", "{", "}", "++", "--",
   "==", "!=", ">=", "<=", ">", "<", "&&", "||", "!",
   ".", "->", "*", "&", "?", ":", "::", "->*", ".*", ";", ",",
   "#", "##", "..." -- preprocessor stuff
}

local keywordHash = {}
for _,v in ipairs(keywordTable) do
   keywordHash[v] = true
end

local punctuatorHash = {}
for _,v in ipairs(punctuatorTable) do
   local l = v:len()
   local b = v:byte()
   punctuatorHash[v] = true
   punctuatorHash[b] = max(l,punctuatorHash[b])
end


-- The following functions test the types of the tokens returned by the tokenizer.
-- They should not be applied to arbitrary strings

local function isSpace(tok)
   return tok and tok:find("^%s") ~= nil end
local function isNewline(tok) -- Subtype of space
   return tok and tok:find("^\n") ~= nil end 
local function isNumber(tok)
   return tok and tok:find("^[.0-9]") ~= nil end
local function isString(tok)
   if tok then return tok:find("^[\'\"]") ~= nil
      or tok:find("^<") and tok:find(">$") end end
local function isPunctuator(tok)
   return tok and punctuatorHash[tok] ~= nil end
local function isIdentifier(tok)
   return tok and tok:find("^[A-Za-z_$]") ~= nil end
local function isKeyword(tok) -- Subtype of identifier
   return tok and keywordHash[tok] ~= nil end
local function isName(tok) -- Subtype of identifier
   return tok and isIdentifier(tok) and not keywordHash[tok] end


-- The tokenizeLine() function takes a line, splits it into tokens,
-- and yields tokens and locations. The number tokens are the weird
-- preprocessor numbers defined by ansi c. The string tokens include
-- character constants and angle-bracket delimited strings occuring
-- after an include directive. Every line begins with a newline
-- token giving the proper indentation. All subsequent spaces
-- are reduced to a single space character.

local function tokenizeLine(options, s, n, notNewline)
   -- little optimization for multiline macros
   -- s may be an array of precomputed tokens
   if type(s) == 'table' then
      return yieldFromArray(options, s, n)
   end
   -- normal operation
   assert(type(s) == 'string')
   local p = s:find("[^%s]")
   -- produce a newline token
   if p and not notNewline then
      local r = '\n' .. s:sub(1,p-1)
      coroutine.yield(r, n)
   end
   -- produce one token
   local function token()
      local b, l, r
      if hasOption(options, "-d:tokenize") then
	 xdebug(n, "[%s][%s]",s:sub(1,p-1),s:sub(p))
      end
      -- space
      l = s:find("[^%s]", p)
      if l == nil then
	 return nil
      elseif l > p then
	 p = l
	 return " ", n
      end
      -- identifier
      r = s:match("^[a-zA-Z_$][a-zA-Z0-9_$]*", p)
      if r ~= nil then
	 p = p + r:len()
	 return r, n
      end
      -- preprocessor numbers
      r = s:match("^%.?[0-9][0-9a-zA-Z._]*", p)
      if r ~= nil then
	 l = r:len()
	 while r:find("[eEpP]$") and s:find("^[-+]", p+l) do
	    r = r .. s:match("^[-+][0-9a-zA-Z._]*", p+l)
	    l = r:len()
	 end
	 p = p + l
	 return r, n
      end
      -- angle-delimited strings in include directives
      b = s:byte(p)
      if b == 60 and s:find("^%s*#%s*include") then
	 r = s:match("^<[^>]+>", p)
	 if r ~= nil then
	    p = p + r:len()
	    return r, n
	 end
      end
      -- punctuator
      l = punctuatorHash[b]
      if l ~= nil then
	 while l > 0 do
	    r = s:sub(p,p+l-1)
	    if punctuatorHash[r] then
	       p = p + l
	       return r, n
	    end
	    l = l - 1
	 end
      end
      -- string
      if b == 34 or b == 39 then -- quotes
	 local q = p
	 repeat
	    q = s:find("[\'\"\\]", q + 1)
	    l = s:byte(q)
	    xassert(q ~= nil, options, n, "Unterminated string or character constant")
	    if l == 92 then
	       q = q + 1
	    end
	 until l == b
	 r = s:sub(p,q)
	 p = q + 1
	 return r, n
      end
      -- error
      xerror(options, n,"Unrecognized character (%s)", s:sub(p))
   end
   -- loop
   if p then
      for tok,tokn in token do
	 coroutine.yield(tok, tokn)
      end
   end
end


-- Obtain lines from coroutine <lines>,
-- and yields their tokens. The coroutine is initialized with
-- argument <options> and all extra arguments.

local function tokenize(options, lines, ...)
   for s,n in wrap(options, lines, ...) do
      tokenizeLine(options, s, n)
   end
end


---------------------------------------------------
---------------------------------------------------
---------------------------------------------------
-- PREPROCESSING 


-- Preprocessing is performed by two coroutines. The first one
-- processes all the preprocessor directives and yields the remaining
-- lines. The second one processes tokens from the remaining lines and
-- perform macro expansions. Both take a table of macro definitions as
-- argument. The first one writes into the table and the second one
-- reads from it.
--
-- Each macro definition is an array of tokens (for a single line
-- macro) or a table whose entry <"lines"> contains an array of arrays
-- of tokens (#defmacro).  f the macro takes arguments, the entry
-- <"args"> contains a list of argument names. If the macro is
-- recursive (#defrecmacro), the entry <recursive> is set.
-- Alternatively, the macro definition may be a function called at
-- macro-expansion time. This provides for complicated situations.


-- forward declarations
local function expandMacros() end
local function processDirectives() end


-- Starting with the second coroutine which takes a token producing
-- coroutine and yields the preprocessed tokens. Argument macros is
-- the macro definition table.

expandMacros = function(options, macros, tokens, ...)
   local ti = wrap(options, tokens, ...)
   local tok, n = ti()
   -- redefine ti() to ensure tok,n remain up-to-date
   local ti = function() tok,n=ti() return tok,n end
   -- create a macro table that is used to process the expansion of
   -- the macro named <symbol>. In general one hides <symbol> to
   -- prevent recursion, except when dealing with a recursive macro...
   local function hideMacro(macros,symbol)
      local nmacros = {}
      setmetatable(nmacros, {__index=macros})
      if macros[symbol] and macros[symbol].recursive then
	 -- limit number of recursive macro invocations
	 if not options.maxrecursion then
	    for _,v in ipairs(options) do
	       if type(v)=='string' and v:find("^%-Zmaxrecursion=") then
		  options.maxrecursion = tonumber(v:match("-Zmaxrecursion=%s*(%d+)%s*$"))
	       end
	    end
	 end
	 -- we use macros[0] to keep track of the recursion count.
	 -- this is not going to collide with any macro symbol because 0 is a number.
	 local maxrecursion = options.maxrecursion or 100
	 nmacros[0] = 1 + (macros[0] or 0) 
	 xassert(nmacros[0] < maxrecursion, options, n,
	 	 "more than %d recursive macro invocations", maxrecursion)
      else
	 -- standard recursion prevention feature
	 nmacros[symbol] = false
      end
      return nmacros
   end
   -- collect one macro arguments into an array
   -- stop when reaching a closing parenthesis or a comma 
   local function collectArgument(ti, varargs)
      local count = 0
      local tokens = {}
      ti()
      while isSpace(tok) do
	 tok = ti()
      end
      while tok do
	 if tok == ')' and count == 0 then
	    break
	 elseif tok == ')' then
	    count = count - 1
	 elseif tok == '(' then
	    count = count + 1
	 elseif tok == ',' and count == 0 and not varargs then
	    break
	 end
	 if isSpace(tok) then tok = " " end
	 tokens[1+#tokens] = tok
	 tok = ti()
      end
      if #tokens > 0 and isSpace(tokens[#tokens]) then
	 tokens[#tokens] = nil
      end
      return tokens
   end
   -- collects all macro arguments
   local function collectArguments(ti,args,ntok,nn)
      local nargs = { [0]={} }
      for _,name in ipairs(args) do
	 if tok == ')' and name == "__VA_ARGS__" then
	    nargs[0][name] = { negComma=true }
	    nargs[name] = { negComma=true }
	 else
	    xassert(tok=='(' or tok==',', options, nn, "not enough arguments for macro '%s'", ntok)
	    local arg = collectArgument(ti, name == "__VA_ARGS__")
	    nargs[0][name] = arg
	    nargs[name] = callAndCollect(options, expandMacros, macros, yieldFromArray, arg, nn)
	 end
      end
      xassert(tok, options, nn, "unterminated arguments for macro '%s'", tok)
      xassert(tok==')', options, nn, "too many arguments for macro '%s'", tok)
      return nargs
   end
   -- coroutine that substitute the macro arguments
   -- and stringification and concatenation are handled here
   local function substituteArguments(options, def, nargs, n, inDirective)
      local uargs = nargs[0] -- unprocessed values
      if inDirective then nargs = uargs end  -- always use unprocessed in directives
      -- prepare loop
      local i,j,k = 1,1,1
      while def[i] do
	 if isSpace(def[i]) then
	    -- copy spaces
	    coroutine.yield(def[i], n)
	 else
	    -- positions j and k on next non-space tokens
	    local function updateJandK()
	       if j <= i then j=i
		  repeat j=j+1 until def[j] == nil or not isSpace(def[j]) end
	       if k <= j then k=j
		  repeat k=k+1 until def[k] == nil or not isSpace(def[k]) end
	    end
	    updateJandK()
	    -- alternatives
	    if def[i]=='#' and def[j] and nargs[def[j]] then
	       -- stringification
	       local v = def[j]
	       local s = string.format("%q", table.concat(uargs[v])):gsub("\\\n","\\n")
	       coroutine.yield(s, n)
	       i = j
	    elseif def[j]=='##' and def[k] and not inDirective then
	       -- concatenation
	       local u = {}
	       local function addToU(s)
		  if nargs[s] then for _,v in ipairs(uargs[s]) do u[1+#u] = v end
		  else u[1+#u]=s end
	       end
	       addToU(def[i])
	       while def[j] == '##' and def[k] do
		  addToU(def[k])
		  i = k
		  updateJandK()
	       end
	       tokenizeLine(options, table.concat(u), n, true)
	    elseif def[i]==',' and def[j]=='__VA_ARGS__' and def[k]==')'
	       and nargs[def[j]].negComma then
	       -- negative comma
	       i = j
	    elseif nargs[def[i]] then
	       -- substitution
	       yieldFromArray(options, nargs[def[i]], n)
	    else
	       -- copy
	       coroutine.yield(def[i], n)
	    end
	 end
	 i = i + 1
      end
   end
   -- main loop
   local newline, directive = true, false
   while tok ~= nil do
      -- detects Zpassed directives
      if newline and tok == '#' then
	 newline, directive = false, true
      elseif not isSpace(tok) then
	 newline = false
      elseif isNewline(tok) then
	 newline, directive = true, false
      end
      -- process code
      local def = macros[tok]
      if not def or directive then
	 -- not a macro
	 coroutine.yield(tok, n)
      elseif type(def) == 'function' then
	 -- magic macro
	 def(ti,tok,n)
      elseif def.args == nil then
	 -- object-like macro
	 local nmacros = hideMacro(macros,tok)
	 expandMacros(options, nmacros, yieldFromArray, def, n)
      elseif def.lines == nil then
	 -- single-line function-like macro
	 local ntok,nn = tok,n
	 repeat ti() until not isSpace(tok)
	 if (tok ~= '(') then
	    coroutine.yield(ntok, nn)
	    coroutine.yield(tok, nn)
	 else
	    local nmacros = hideMacro(macros,ntok)
	    local nargs = collectArguments(ti,def.args,ntok,nn)
	    expandMacros(options, nmacros, substituteArguments, def, nargs, nn)
	 end
      else
	 -- multi-line function-like macro
	 local ntok,nn = tok,n
	 repeat ti() until not isSpace(tok)
	 if (tok ~= '(') then
	    coroutine.yield(ntok, nn)
	    coroutine.yield(tok, nn)
	 else
	    local lines = def.lines
	    local nargs = collectArguments(ti,def.args,ntok,nn)
	    local nmacros = hideMacro(macros,ntok)
	    -- a coroutine that yields the macro definition
	    local function yieldMacroLines()
	       local count = 0
	       for i=1,#lines,2 do
		  local ls,ln = lines[i], lines[i+1]
 		  -- are we possibly in a cpp directive
		  local dir = false
		  if ls[2] and ls[2]:find('^#') then
		     dir = isIdentifier(ls[3]) and ls[3] or ls[4]
		  end
		  if dir and nargs[dir] then
		     dir = false      -- leading stringification
		  elseif dir == 'defmacro' then
		     count = count + 1  -- entering a multiline macto
		  elseif dir == 'endmacro' then
		     count = count - 1  -- leaving a multiline macro
		  end
		  dir = dir or count > 0
		  -- substitute
		  --print(string.format("<<< [%s]",table.concat(ls,"|",2)))
		  ls = callAndCollect(options,substituteArguments,ls,nargs,ln,dir)
		  --print(string.format(">>> [%s]",table.concat(ls,"|",2)))
		  -- compute lines (optimize speed by passing body lines as tokens)
		  if ls[2] and ls[2]:find("^#") then -- but not directives
		     ls = ls[1]:sub(2) .. table.concat(ls, nil, 2)
		  end
		  coroutine.yield(ls,ln)
	       end
	    end
	    -- reenter the preprocessing subroutines
	    expandMacros(options, nmacros,
			 tokenize, processDirectives, nmacros,
			 yieldMacroLines)
	 end
      end
      ti()
   end
end


-- Processing conditional directive requires evaluating conditions
-- This function takes an iterator on preprocessed expression tokens
-- and computes the value. This does not handle defined(X) expressions.
-- Optional argument resolver is a function that takes an indentifer
-- name and returns a value. Otherwise zero is assumed

local function evaluateCppExpression(options, tokenIterator, n, resolver)
   -- redefine token iterator to skip spaces and update tok
   local tok
   local function ti()
      repeat tok = tokenIterator()
      until not isSpace(tok) return tok
   end
   -- operator tables
   local unaryOps = {
      ["!"] = function(v) return v == 0 and 1 or 0 end,
      ["~"] = function(v) return bit.bnot(v) end,
      ["+"] = function(v) return v end,
      ["-"] = function(v) return -v end
   }
   local binaryOps = {
      ["*"] = function(a,b) return a * b end,
      ["/"] = function(a,b) xassert(b~=0,options,n,"division by zero"); return math.floor(a / b) end,
      ["%"] = function(a,b) xassert(b~=0,options,n,"division by zero"); return a % b end,
      ["+"] = function(a,b) return a + b end,
      ["-"] = function(a,b) return a - b end,
      [">>"] = function(a,b) return bit.lshift(a, -b) end,
      ["<<"] = function(a,b) return bit.lshift(a, b) end,
      [">="] = function(a,b) return a >= b and 1 or 0 end,
      ["<="] = function(a,b) return a <= b and 1 or 0 end,
      [">"] = function(a,b) return a > b and 1 or 0 end,
      ["<"] = function(a,b) return a < b and 1 or 0 end,
      ["=="] = function(a,b) return a == b and 1 or 0 end,
      ["!="] = function(a,b) return a ~= b and 1 or 0 end,	 
      ["&"] = function(a,b) return bit.band(a,b) end,
      ["^"] = function(a,b) return bit.bxor(a,b) end,
      ["|"] = function(a,b) return bit.bor(a,b) end,
      ["&&"] = function(a,b) return (a ~= 0 and b ~= 0) and 1 or 0 end,
      ["||"] = function(a,b) return (a ~= 0 or b ~= 0) and 1 or 0 end,
   }
   local binaryPrec = {
      ["*"] = 1, ["/"] = 1, ["%"] = 1,
      ["+"] = 2, ["-"] = 2,
      [">>"] = 3, ["<<"] = 3,
      [">="] = 4, ["<="] = 4, ["<"] = 4, [">"] = 4,
      ["=="] = 5, ["!="] = 5,
      ["&"] = 6, ["^"] = 7, ["|"] = 8,
      ["&&"] = 9, ["||"] = 10
   }
   -- forward
   local function evaluate() end
   -- unary operations
   local function evalUnary()
      if unaryOps[tok] then
	 local op = unaryOps[tok]
	 ti(); return op(evalUnary())
      elseif tok == '(' then
	 ti(); local v = evaluate()
	 xassert(tok == ')', options, n, "missing closing parenthesis")
	 ti(); return v
      elseif tok == 'defined' then -- magic macro should have removed this
	 xerror(options, n, "syntax error after <defined>")
      elseif isIdentifier(tok) then
         local v = type(resolver) == 'function' and resolver(tok,ti)
	 ti(); return v or 0
      elseif isNumber(tok) then
	 local v = tok:gsub("[ULul]+$","")
	 if v:find("^0[0-7]+$") then
	    v = tonumber(v,8) -- octal
	 elseif v:find("^0[bB][01]+") then
	    v = tonumber(v:sub(3),2) -- binary
	 else
	    v = tonumber(v) -- lua does the rest
	 end
	 xassert(v and v == math.floor(v), options, n, "syntax error (invalid integer '%s')", tok)
	 ti(); return v
      elseif isString(tok) then
	 local v = '""'
	 if tok:find("^'") then -- interpret character constant as number
	    v = evalLuaExpression(string.format("return string.byte(%s)", tok))
	    xassert(type(v)=='number', options, n, "syntax error (invalid value '%s')", tok)
	    ti()
	 else
	    while isString(tok) do
	       xassert(tok:find('^"'), options, n, "syntax error (invalid value '%s')", tok)
	       v = v:gsub('"$','') .. tok:gsub('^"','')
	       ti()
	    end
	 end
	 return v
      end
      xerror(options, n, "syntax error (invalid value '%s')", tok)
   end
   -- binary operations
   local function evalBinary(p)
      if p == 0 then
	 return evalUnary()
      else
	 local val = evalBinary(p-1)
	 while binaryPrec[tok] == p do
	    local op = binaryOps[tok]  ti()
	    local oval = evalBinary(p-1)
	    xassert(p==4 or p==5 or type(val)=='number', options, n,
		    "expression uses arithmetic operators on strings")
	    xassert(type(val) == type(oval), options, n,
		    "expression compares numbers and strings")
	    val = op(val,oval)
	 end
	 return val
      end
   end
   -- eval ternary conditonal
   local function evalTernary()
      local c = evalBinary(10)
      if tok ~= '?' then return c end
      ti() local v1 = evalBinary(10)
      xassert(tok == ':', options, n, "expecting ':' after '?'")
      ti() local v2 = evalBinary(10)
      if c == 0 then return v2 else return v1 end
   end

   -- actual definition of evaluate
   evaluate = function()
      return evalTernary()
   end
   -- main function
   ti()
   xassert(tok, options, n, "constant expression expected");
   local result = evaluate()
   if hasOption(options, "-d:eval") then
      xdebug(n, "eval %s", result)
   end
   -- warn about garbage when called from cpp (but not when called with resolver)
   xassert(resolver or not tok, options, n, "garbage after conditional expression");
   return result
end


-- Now dealing with the coroutine that processes all directives.
-- This coroutine obtains lines from coroutine <lines>,
-- processes all directives, and yields remaining lines

processDirectives = function(options, macros, lines, ...)
   local li = wrap(options, lines, ...)
   local s, n = li()
   -- redefine li to make sure vars s and n are up-to-date
   local li = function() s,n=li() return s,n end
   -- directives store their current token in these vars
   local dirtok, tok, spc
   -- forward declaration
   local processLine
   -- the captureTable mechanism communicates certain preprocessor
   -- events to the declaration parser in order to report them
   -- to the user (the parsing does not depend on this).
   -- if macros[1] is a table, the preprocessor will append
   -- records to this table for the parser to process.
   local function hasCaptureTable()
      local captable = rawget(macros,1)
      return captable and type(captable)=='table' and captable
   end
   local function addToCaptureTable(record)
      local captable = hasCaptureTable()
{'fraction_non_alphanumeric': 0.16738184591002198, 'fraction_numerical': 0.00903069539344826, 'mean_word_length': 2.461904761904762, 'pattern_counts': {'":': 4, '<': 116, '<?xml version=': 0, '>': 122, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4684438', 'n_tokens_mistral': 22511, 'n_tokens_neox': 21166, 'n_words': 7365}