Lift the #-shaped length foreigns to a unary length primop - #341

Closes #247.

The problem

pslua compiles PureScript to Lua. A PureScript function implemented in Lua (an FFI import, "foreign" in PureScript's vocabulary) is opaque to the compiler's optimizer: the optimizer works on an intermediate representation (IR) where a foreign body is just text it cannot look inside. The foreign lifter (Language.PureScript.Backend.Lua.ForeignLift) exists to reopen a slice of that box — it parses the fork's real .lua source and, for an allowlisted export whose body falls in a small pure subset, translates the body into IR nodes so ordinary rewriting can proceed.

The length exports of the Lua forks are the tiniest possible foreigns. Verbatim from purescript-lua-arrays' src/Data/Array.lua:

  length = (function(xs) return #xs end),

# is Lua's unary length operator: one VM opcode. purescript-lua-strings' Data.String.CodeUnits.length is the same body over a string. So a saturated length xs was paying a table read off the foreign module plus a call frame to reach an opcode — and unlike a show shim, length sits on hot paths: it appears in loop guards and bounds logic, once per iteration.

The lifter could not translate these because its only unary case was not:

  UnOp LogicalNot (_ann, a) → primNot <$> liftLuaExp env bound a

What changed

One case for #, and two allowlist entries:

  UnOp LogicalNot (_ann, a) → primNot <$> liftLuaExp env bound a
  UnOp HashOp (_ann, a) → primLen <$> liftLuaExp env bound a

      ("Data.Array", ["length"])
    , ("Data.String.CodeUnits", ["length"])

The allowlist is a hard contract in this pass: a listed export that stops being liftable (a fork reshapes its body) is a compile error, not a silent regression. So these two entries also pin the fork sources.

The node is the existing # node, renamed

The issue proposed adding a new PrimLen node. The IR already had a node that lowers to exactly # — ArrayLength, minted by the array-pattern matcher for a fixed-length array match — so adding a second one would mean two IR nodes for one Lua operator, and every rewrite keyed on # would need writing twice or would silently miss whichever node it did not name. Instead the existing node is renamed to PrimLen and documented as the second unary primop of Note [IR primops], beside PrimNot. Its position in RawExp is unchanged, so the derived Ord instance is unaffected.

The payoff is that lifted length reads inherit, unchanged, every rule the array-pattern length test already had. All four fire in this PR's goldens: the fold over a manifest array, the push into if branches, the CSE candidate class, and the Deref inlining tier that pastes a cheap read at its use sites.

What the generated Lua looks like

New golden Golden.LengthLift. A saturated array length and a string length become the bare operator:

M.Golden_LengthLift_Test_countOf = function(xs_S_0) return #(xs_S_0) end
M.Golden_LengthLift_Test_widthOf = function(s_S_0) return #(s_S_0) end

The loop-guard case — the shape the lift exists for, where the call frame was paid per iteration:

M.Golden_LengthLift_Test_countBelow = function(xs)
  local acc, i
  acc, i = 0, 0
  while true do
    if i < #(xs) then acc, i = acc + i, i + 1 else return acc end
  end
end

An existing golden, Golden.StringCodePoints, shows the effect on real code. Both foreign tables shed their length row, and one of them vanishes outright (- is the previous golden, + the new one):

-local Data_Array_foreign = { length = function(xs) return #(xs) end }
-  length = function(s) return #(s) end,
-local Data_String_CodeUnits_length = Data_String_CodeUnits_foreign.length

and its call sites become the operator, with the repeat inside one body shared by CSE:

-  if Data_String_CodeUnits_length(s) == 0 then
+  if #(s) == 0 then
-  return Data_String_CodeUnits_foreign.drop(Data_String_CodeUnits_length(Data_String_CodePoints_take_S_w(n, s)))(s)
+  return Data_String_CodeUnits_foreign.drop(#(Data_String_CodePoints_take_S_w(n, s)))(s)
+  local _S_cse0 = #(s_S_0)

Every eval/golden.txt execution oracle in the suite is unchanged, which is the semantic check that these are the same programs.

Data.Array.ST.lengthImpl stays off the allowlist

The issue asked for three exports. The third, Data.Array.ST.lengthImpl, has a byte-identical body:

  lengthImpl = (function(xs) return #xs end),

It is nonetheless excluded, and the exclusion is measured rather than assumed — I allowlisted it and looked at the output. Its PureScript type is STFn1 (STArray h a) h Int, an effectful uncurried function, so a call of it is an effect statement that the compiler wraps in a thunk. Code generation sheds that thunk only when the thunk's body is a call; a lifted length body is not, so the thunk survives:

  local before = (function() return #(arr) end)()   -- lengthImpl allowlisted
  local before = Data_Array_ST_lengthImpl(arr)      -- as shipped

That is a closure allocation on top of the call it was supposed to replace — a pessimization, so the exclusion costs nothing and saves something.

There is a second reason, stated as an invariant rather than a live bug. PrimLen is treated as a stable read: CSE may collapse two occurrences into one binding, and the Deref tier pastes a bound one at its use sites regardless of use count. Neither move is meaning-preserving if the operand's length can change in between, and an STArray's can — #arr before a push and after it are different numbers. Today the unshed thunk keeps a lifted lengthImpl out of those rules' reach (I verified this: with lengthImpl allowlisted, CSE shares the thunk, local _S_cse0 = function() return #(arr) end, and both sites still call it, so the execution oracle stays correct). The exclusion does not lean on that accident. Note [PrimLen reads immutable values] records the invariant and is cross-referenced from the two rules that depend on it, so a future producer of the node has to check its operand.

Golden.LengthLift pins this: lengthsAroundPush brackets a push with two Data.Array.ST.length reads, and its Lua golden holds both at a direct Data_Array_ST_lengthImpl(arr), so allowlisting the export later trips the golden.

Also in here

The allowlist Haddock claimed "a broader allowlist is follow-up work (issue #187)". #187 is the closing audit of the optimisation series, not an allowlist issue, and no issue tracks broadening the list. Rather than repoint it at #247 — which this PR closes, so it would be a fresh dead pointer — the sentence now states the follow-up without a number.

Verification

• Two focused lifter specs, mirroring the existing runFn ones: the # body lifts to PrimLen, and a # body with a preceding local declines (the pure-return-tree restriction still bounds the new operator). Confirmed red before the lifter case — expected: Just (AbsN … (PrimLen …)) / but got: Nothing — and green after.
• cabal test all: 1221 examples, 0 failures. Green on a re-run with no PSLUA_GOLDEN_ACCEPT, so the accepted goldens are stable.
• Seed-stressed for the randomized property tests, since the change touches the optimizer's node set: IR Optimizer 12 runs and all non-golden specs 12 runs, fresh seeds, no failures.
• fourmolu, hlint (no hints), and a cabal clean full rebuild with zero warnings. luacheck on the new golden reports only the two classes every golden already carries (the unread M table, a long line).