Difficulties byte-compiling very large .el file

Difficulties byte-compiling very large .el file

[Aemon Cannon]

This is a re-post of a question I asked of gnu.emacs.help. Xah Lee
suggested I try this mailing list.
-------------------------------------------------------------------------------------------------------

I've been working on a project to create an elisp target for the ANTLR
parser-generator. Here's the project page:
http://github.com/aemoncannon/antlr-elisp/tree/experimental

The generated parser for ActionScript 3 is over 30k lines long and
fails to byte-compile with the message in Emacs 22:
as3_elispParser.el:31515:33:Error: Invalid character: 256, #o400,
#x100

..and this message in Emacs 23:
../test/grammars/as3_elispParser.el:31515:33:Error: Args out of range:
256, 0, 255

Here's the source in question: http://aemon.com/file_dump/as3_elispParser.el

If you're interested in trying to compile, you'll need:
http://github.com/aemoncannon/antlr-elisp/raw/c411f29743e3182523e0ad27a9384b6c4210d55e/src/runtime/ELisp/a3el-runtime.el

I don't think the error is actually related to the content of the
file, as there are no non-ascii characters in the file, and deleting
seemingly arbitrary chunks makes the error go away.

There are lots of "Warning: reference to free variable ...." warnings,
but I understand where those are coming from and I'm not worried about
them.

Bear in mind there are *lots* of macros being expanded. Most of the
forms with the prefix 'a3el' are macros.

Any ideas?

Re: Difficulties byte-compiling very large .el file

[Andreas Schwab]

Aemon Cannon <aemoncannon@gmail.com> writes:

> The generated parser for ActionScript 3 is over 30k lines long and
> fails to byte-compile with the message in Emacs 22:
> as3_elispParser.el:31515:33:Error: Invalid character: 256, #o400,
> #x100
>
> ..and this message in Emacs 23:
> ../test/grammars/as3_elispParser.el:31515:33:Error: Args out of range:
> 256, 0, 255

Probably the bytecode string is becoming too large so that a byte-goto
operand overflows.  Try this patch to verify:

--- lisp/emacs-lisp/bytecomp.el.~2.248.~	2009-08-06 13:15:39.000000000 +0200
+++ lisp/emacs-lisp/bytecomp.el	2009-08-20 10:26:05.000000000 +0200
@@ -853,7 +853,8 @@ otherwise pop it")
 	      (t			; Absolute jump
 	       (setq pc (car (cdr (car bytes))))	; Pick PC from tag
 	       (setcar (cdr bytes) (logand pc 255))
-	       (setcar bytes (lsh pc -8))))
+	       (setcar bytes (lsh pc -8))
+	       (if (> (car bytes) 255) (error "Bytecode overflow"))))
 	(setq patchlist (cdr patchlist))))
     (apply 'unibyte-string (nreverse bytes))))
 

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Difficulties byte-compiling very large .el file

[Aemon Cannon]

Bingo!
../test/grammars/as3_elispParser.el:31515:33:Error: Bytecode overflow

I'm not super familiar with emacs byte-compiling, but my guess is that
increasing
the size of the operands is not an option. Should I look for a
conditional that spans
a lot of code, and try to fix it that way?

Thoughts?



On Thu, Aug 20, 2009 at 4:27 AM, Andreas Schwab<schwab@linux-m68k.org> wrote:
> Aemon Cannon <aemoncannon@gmail.com> writes:
>
>> The generated parser for ActionScript 3 is over 30k lines long and
>> fails to byte-compile with the message in Emacs 22:
>> as3_elispParser.el:31515:33:Error: Invalid character: 256, #o400,
>> #x100
>>
>> ..and this message in Emacs 23:
>> ../test/grammars/as3_elispParser.el:31515:33:Error: Args out of range:
>> 256, 0, 255
>
> Probably the bytecode string is becoming too large so that a byte-goto
> operand overflows.  Try this patch to verify:
>
> --- lisp/emacs-lisp/bytecomp.el.~2.248.~        2009-08-06 13:15:39.000000000 +0200
> +++ lisp/emacs-lisp/bytecomp.el 2009-08-20 10:26:05.000000000 +0200
> @@ -853,7 +853,8 @@ otherwise pop it")
>              (t                        ; Absolute jump
>               (setq pc (car (cdr (car bytes))))        ; Pick PC from tag
>               (setcar (cdr bytes) (logand pc 255))
> -              (setcar bytes (lsh pc -8))))
> +              (setcar bytes (lsh pc -8))
> +              (if (> (car bytes) 255) (error "Bytecode overflow"))))
>        (setq patchlist (cdr patchlist))))
>     (apply 'unibyte-string (nreverse bytes))))
>
>
> Andreas.
>
> --
> Andreas Schwab, schwab@linux-m68k.org
> GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
> "And now for something completely different."
>

Re: Difficulties byte-compiling very large .el file

[Andreas Schwab]

Aemon Cannon <aemoncannon@gmail.com> writes:

> Should I look for a conditional that spans a lot of code, and try to
> fix it that way?

Use less macros.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Difficulties byte-compiling very large .el file

[Aemon Cannon]

I can't really do that.

The idea is for these parsers to be used interactively in language
modes, so they need to be fast.
Macro use has been crucial in this area.

Also, ActionScript 3 is not the most complicated grammar in the world.
What happens when a bigger
parser overflows my guess for the value of 'less' ?


On Thu, Aug 20, 2009 at 9:23 AM, Andreas Schwab<schwab@linux-m68k.org> wrote:
> Aemon Cannon <aemoncannon@gmail.com> writes:
>
>> Should I look for a conditional that spans a lot of code, and try to
>> fix it that way?
>
> Use less macros.
>
> Andreas.
>
> --
> Andreas Schwab, schwab@linux-m68k.org
> GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
> "And now for something completely different."
>

Re: Difficulties byte-compiling very large .el file

[Eli Zaretskii]

> Date: Thu, 20 Aug 2009 09:07:01 -0400
> From: Aemon Cannon <aemoncannon@gmail.com>
> Cc: emacs-devel@gnu.org
> 
> Bingo!
> ../test/grammars/as3_elispParser.el:31515:33:Error: Bytecode overflow
> 
> I'm not super familiar with emacs byte-compiling, but my guess is that
> increasing
> the size of the operands is not an option. Should I look for a
> conditional that spans
> a lot of code, and try to fix it that way?
> 
> Thoughts?

Submit a bug report ("M-x report-emacs-bug RET") and someone will take
care of it.

Re: Difficulties byte-compiling very large .el file

[Aidan Kehoe]

 Ar an naoú lá déag de mí Lúnasa, scríobh Aemon Cannon: 

 > [...] Here's the source in question:
 > http://aemon.com/file_dump/as3_elispParser.el
 > 
 > If you're interested in trying to compile, you'll need:
 > http://github.com/aemoncannon/antlr-elisp/raw/c411f29743e3182523e0ad27a9384b6c4210d55e/src/runtime/ELisp/a3el-runtime.el
 > 
 > I don't think the error is actually related to the content of the
 > file, as there are no non-ascii characters in the file, and deleting
 > seemingly arbitrary chunks makes the error go away.

Tangentially to this, you should be aware that several of your integer
constants are silently overflowing in that file. With an XEmacs with 31-bit
integers and no bignum support, the Lisp reader throws an overflow error
twice for me; GNU Emacs has (IIRC) 27-bit integers on 32-bit platforms and
doesn’t error on reading integers it can’t represent, so more than two of
your integer constants may be corrupt. 

The constants that overflow for me are 2147483647 on line 10006 and again on
line 2291. I can work around this (though there’s still lots of thrashing
when compiling the file) by using most-positive-fixnum instead, modifying
#'a3el-lookahead-let-bindings to call #'symbol-value on max-k if it doesn’t
satisfy #'numberp.

-- 
¿Dónde estará ahora mi sobrino Yoghurtu Nghe, que tuvo que huir
precipitadamente de la aldea por culpa de la escasez de rinocerontes?

Re: Difficulties byte-compiling very large .el file

[Miles Bader]

Aidan Kehoe <kehoea@parhasard.net> writes:
> GNU Emacs has (IIRC) 27-bit integers on 32-bit platforms

``The range of values for integers in Emacs Lisp is -268435456 to
268435455 (29 bits; i.e., -2**28 to 2**28 - 1) on most machines.''

-Miles

-- 
Bride, n. A woman with a fine prospect of happiness behind her.

Re: Difficulties byte-compiling very large .el file

[Aidan Kehoe]

 Ar an cúigiú lá is fiche de mí Lúnasa, scríobh Miles Bader: 

 > Aidan Kehoe <kehoea@parhasard.net> writes:
 > > GNU Emacs has (IIRC) 27-bit integers on 32-bit platforms
 > 
 > ``The range of values for integers in Emacs Lisp is -268435456 to
 > 268435455 (29 bits; i.e., -2**28 to 2**28 - 1) on most machines.''

Thanks for the correction. Aemon’s problem remains, though, independent of
that. Is there a good reason you don’t error on encountering integers the
emacs binary can’t represent? Portable code needs to be prepared for that
anyway.

-- 
¿Dónde estará ahora mi sobrino Yoghurtu Nghe, que tuvo que huir
precipitadamente de la aldea por culpa de la escasez de rinocerontes?

Re: Difficulties byte-compiling very large .el file

[Aemon Cannon]

[-- Attachment #1: Type: text/plain, Size: 2840 bytes --]

Aidan,
Thanks for pointing out the overflow issue. As you may have guessed, those
constants are both max-value for a signed 32 bit integer, which is what
ANTLR spits out in LL* situations (unbounded values for max-k). I may be
able to specify the max value for elisp in the ANTLR template....

RE: My original problem,
I narrowed it down a bit and submitted a report at:
http://emacsbugs.donarmstrong.com/cgi-bin/bugreport.cgi?bug=4251
I've since sent a followup with the following code, that also fails:
;;----------------

(defmacro many-forms ()
  (let ((body '()))
    (dotimes (i 20000)
      (setq body (cons '(message "more") body)))
    `(progn ,@body)))

(many-forms)

(if (eq 1 a)
    (message "dude")
  (message "else"))

;;--------------

I had assumed that the goto opcode used a 16 bit relative offset, but this
snippet seems to indicate that it's not relative to the conditional itself.
I also noticed in bytecode.c that the goto opcodes all use:
.....
stack.pc = stack.byte_string_start + op;
.....
where 'op' is a 16 bit int. This indicates that the jump is measured in
relation to the top of the current byte_string, so if the conditional is in
its own byte_string, it should work:
;;--------------------
(defmacro many-forms ()
  (let ((body '()))
    (dotimes (i 20000)
      (setq body (cons '(message "more") body)))
    `(progn ,@body)))

(many-forms)

(defun bar ()
  (if (eq 1 a)
      (message "dude")
    (message "else")))

;; ----------------------------

Which does work. Wrapping in lambda also works.

So now I'm thinking that as3_elispParser.el must have a single function body
whose bytecode overflows the 16bit limit. As removing chunks of code from
the top-level seems to alleviate the error (the lines with
(a3el-parser-bitset ..) for instance), I'm guessing that the problematic
byte_string corresponds to the top-level of the file.

I may be able to wrap this top-level setup code into smaller functions....











On Tue, Aug 25, 2009 at 7:50 AM, Aidan Kehoe <kehoea@parhasard.net> wrote:

>
>  Ar an cúigiú lá is fiche de mí Lúnasa, scríobh Miles Bader:
>
>  > Aidan Kehoe <kehoea@parhasard.net> writes:
>  > > GNU Emacs has (IIRC) 27-bit integers on 32-bit platforms
>  >
>  > ``The range of values for integers in Emacs Lisp is -268435456 to
>  > 268435455 (29 bits; i.e., -2**28 to 2**28 - 1) on most machines.''
>
> Thanks for the correction. Aemon’s problem remains, though, independent of
> that. Is there a good reason you don’t error on encountering integers the
> emacs binary can’t represent? Portable code needs to be prepared for that
> anyway.
>
> --
> ¿Dónde estará ahora mi sobrino Yoghurtu Nghe, que tuvo que huir
> precipitadamente de la aldea por culpa de la escasez de rinocerontes?
>

[-- Attachment #2: Type: text/html, Size: 3580 bytes --]

Re: Difficulties byte-compiling very large .el file

[Stefan Monnier]

> Tangentially to this, you should be aware that several of your integer
> constants are silently overflowing in that file. With an XEmacs with 31-bit

Good point.  I've installed a few changes which should now handle this
a bit better (partly by using floats to represent larger integers, as
we already did in string-to-number, partly by detecting overflows).


        Stefan

Re: Difficulties byte-compiling very large .el file

[Aemon Cannon]

[-- Attachment #1: Type: text/plain, Size: 3427 bytes --]

To followup:

I'm now working around the original issue by wrapping parts of the generated
parser in in lambdas thusly:

(defmacro a3el-do-in-thunk (&rest body)
  (let ((thunk-name (gensym "thunk")))
    `(progn
       (setq ,thunk-name (lambda () ,@body))
       (funcall ,thunk-name))))

Works like a charm.
Thanks to everyone for the help.

On Tue, Aug 25, 2009 at 11:04 AM, Aemon Cannon <aemoncannon@gmail.com>wrote:

> Aidan,
> Thanks for pointing out the overflow issue. As you may have guessed, those
> constants are both max-value for a signed 32 bit integer, which is what
> ANTLR spits out in LL* situations (unbounded values for max-k). I may be
> able to specify the max value for elisp in the ANTLR template....
>
> RE: My original problem,
> I narrowed it down a bit and submitted a report at:
> http://emacsbugs.donarmstrong.com/cgi-bin/bugreport.cgi?bug=4251
> I've since sent a followup with the following code, that also fails:
> ;;----------------
>
> (defmacro many-forms ()
>   (let ((body '()))
>     (dotimes (i 20000)
>       (setq body (cons '(message "more") body)))
>     `(progn ,@body)))
>
> (many-forms)
>
> (if (eq 1 a)
>     (message "dude")
>   (message "else"))
>
> ;;--------------
>
> I had assumed that the goto opcode used a 16 bit relative offset, but this
> snippet seems to indicate that it's not relative to the conditional itself.
> I also noticed in bytecode.c that the goto opcodes all use:
> .....
> stack.pc = stack.byte_string_start + op;
> .....
> where 'op' is a 16 bit int. This indicates that the jump is measured in
> relation to the top of the current byte_string, so if the conditional is in
> its own byte_string, it should work:
> ;;--------------------
> (defmacro many-forms ()
>   (let ((body '()))
>     (dotimes (i 20000)
>       (setq body (cons '(message "more") body)))
>     `(progn ,@body)))
>
> (many-forms)
>
> (defun bar ()
>   (if (eq 1 a)
>       (message "dude")
>     (message "else")))
>
> ;; ----------------------------
>
> Which does work. Wrapping in lambda also works.
>
> So now I'm thinking that as3_elispParser.el must have a single function
> body whose bytecode overflows the 16bit limit. As removing chunks of code
> from the top-level seems to alleviate the error (the lines with
> (a3el-parser-bitset ..) for instance), I'm guessing that the problematic
> byte_string corresponds to the top-level of the file.
>
> I may be able to wrap this top-level setup code into smaller functions....
>
>
>
>
>
>
>
>
>
>
>
>
> On Tue, Aug 25, 2009 at 7:50 AM, Aidan Kehoe <kehoea@parhasard.net> wrote:
>
>>
>>  Ar an cúigiú lá is fiche de mí Lúnasa, scríobh Miles Bader:
>>
>>  > Aidan Kehoe <kehoea@parhasard.net> writes:
>>  > > GNU Emacs has (IIRC) 27-bit integers on 32-bit platforms
>>  >
>>  > ``The range of values for integers in Emacs Lisp is -268435456 to
>>  > 268435455 (29 bits; i.e., -2**28 to 2**28 - 1) on most machines.''
>>
>> Thanks for the correction. Aemon’s problem remains, though, independent of
>> that. Is there a good reason you don’t error on encountering integers the
>> emacs binary can’t represent? Portable code needs to be prepared for that
>> anyway.
>>
>> --
>> ¿Dónde estará ahora mi sobrino Yoghurtu Nghe, que tuvo que huir
>> precipitadamente de la aldea por culpa de la escasez de rinocerontes?
>>
>
>

[-- Attachment #2: Type: text/html, Size: 4394 bytes --]