Bug: self require -> stack overflow

[ntupel]

(ns test
(:require test))

results in:

clojure.lang.Compiler$CompilerException: test.clj:0: null
at clojure.lang.Compiler.analyzeSeq(Compiler.java:3824)
at clojure.lang.Compiler.analyze(Compiler.java:3657)
at clojure.lang.Compiler.eval(Compiler.java:3848)
at clojure.lang.Compiler.load(Compiler.java:4151)
at clojure.lang.RT.loadResourceScript(RT.java:360)
at clojure.lang.RT.loadResourceScript(RT.java:347)
at clojure.lang.RT.loadResourceScript(RT.java:339)
at clojure.load_resources__1744.doInvoke(boot.clj:3209)
at clojure.lang.RestFn.invoke(RestFn.java:413)
at clojure.load_one__1707.invoke(boot.clj:3058)
at clojure.load_lib__1727.doInvoke(boot.clj:3095)
at clojure.lang.RestFn.applyTo(RestFn.java:147)
at clojure.apply__135.doInvoke(boot.clj:364)
at clojure.lang.RestFn.invoke(RestFn.java:443)
at clojure.load_libs__1731.doInvoke(boot.clj:3121)
at clojure.lang.RestFn.applyTo(RestFn.java:142)
at clojure.apply__135.doInvoke(boot.clj:364)
at clojure.lang.RestFn.invoke(RestFn.java:443)
at clojure.require__1735.doInvoke(boot.clj:3181)
at clojure.lang.RestFn.invoke(RestFn.java:413)
at test.eval__3068.invoke(test.clj:1)
...
Caused by: java.lang.StackOverflowError
at java.lang.ClassLoader.defineClass1(Native Method)
at java.lang.ClassLoader.defineClass(ClassLoader.java:620)
at java.lang.ClassLoader.defineClass(ClassLoader.java:465)
at clojure.lang.DynamicClassLoader.defineClass(DynamicClassLoader.java:39)
at clojure.lang.Compiler$FnExpr.compile(Compiler.java:2986)
at clojure.lang.Compiler$FnExpr.parse(Compiler.java:2773)
at clojure.lang.Compiler.analyzeSeq(Compiler.java:3815)
at clojure.lang.Compiler.analyze(Compiler.java:3657)
at clojure.lang.Compiler.eval(Compiler.java:3848)
at clojure.lang.Compiler.load(Compiler.java:4151)
at clojure.lang.RT.loadResourceScript(RT.java:360)
at clojure.lang.RT.loadResourceScript(RT.java:347)
at clojure.lang.RT.loadResourceScript(RT.java:339)
at clojure.load_resources__1744.doInvoke(boot.clj:3209)
at clojure.lang.RestFn.invoke(RestFn.java:413)
at clojure.load_one__1707.invoke(boot.clj:3058)
at clojure.load_lib__1727.doInvoke(boot.clj:3095)
at clojure.lang.RestFn.applyTo(RestFn.java:147)
at clojure.apply__135.doInvoke(boot.clj:364)
at clojure.lang.RestFn.invoke(RestFn.java:443)
at clojure.load_libs__1731.doInvoke(boot.clj:3121)
at clojure.lang.RestFn.applyTo(RestFn.java:142)
at clojure.apply__135.doInvoke(boot.clj:364)
at clojure.lang.RestFn.invoke(RestFn.java:443)
at clojure.require__1735.doInvoke(boot.clj:3181)
at clojure.lang.RestFn.invoke(RestFn.java:413)
at test.eval__3068.invoke(test.clj:1)
...

[Rich Hickey]

On Sep 8, 4:08 pm, ntupel <ntu...@googlemail.com> wrote:
> (ns test
> (:require test))
>
> results in:
>
> clojure.lang.Compiler$CompilerException: test.clj:0: null

...
> Caused by: java.lang.StackOverflowError

Hmm, don't do that?

Seriously, how is this a bug in Clojure, and not a bug in your
program, which resulted in an exception which easily leads you to your
problem?

Rich

[ntupel]

On Mon, 2008-09-08 at 13:15 -0700, Rich Hickey wrote:
> Hmm, don't do that?
>
> Seriously, how is this a bug in Clojure, and not a bug in your
> program, which resulted in an exception which easily leads you to your
> problem?

Well, first of all this bug in a users program results in undefined
behavior in the Clojure compiler which terminates due to a resource
exhaustion without any particular error message. This should never
happen.

Then, please note that this somewhat contrived example, when extended to
circular requires, e.g. A requires B and B requires A might accidentally
(or by bad design) occur during development. One can argue whether this
should result in an error message or whether the semantics of require
are satisfied if the namespaces are loaded once each. But again, a
StackOverflowError and a "don't do that" can not be the answer.

My 2 Cents.

[Brett Morgan]

Unless I miss my guess, you are actually staring down the barrel of
some reasonably old computer science. You seem to be asking for the
compiler to be able to prove that your computation finishes, and if it
doesn't then give you a sane response.

Gödel, Escher, Bach by Douglas Hofstadter is a good starting point.

http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach

--

Brett Morgan http://brett.morgan.googlepages.com/

[ntu...@googlemail.com]

On Sep 9, 8:48 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
> You seem to be asking for the
> compiler to be able to prove that your computation finishes, and if it
> doesn't then give you a sane response.

No.

[Brett Morgan]

Would you kindly educate me in how you believe that Clojure would go
about trapping your error and giving you an error message instead of
running out of stack space, given that you had given it a
non-terminating dependency list?

[ntu...@googlemail.com]

On Sep 9, 10:51 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
> Would you kindly educate me in how you believe that Clojure would go
> about trapping your error and giving you an error message instead of
> running out of stack space, given that you had given it a
> non-terminating dependency list?

First please note that circular includes are nothing specific to
Clojure and other compilers have solved this problem multiple times
already.
Second I am not insisting on a error message. As I said, the precise
semantics of require can be debated. For instance the ns macro can
always check a set of declared ns symbols before processing the ns
declaration further, putting a new ns symbol into this set as soon as
it is encountered. Wheather it silently stops then or issues an error
message is up to discussion. Also note that this is not a concrete
suggestion how to implement the ns macro, it should just illustrate
that this is not an instance of the halting problem.

[Mike Hinchey]

It doesn't seem *impossible* for require and use to keep a var set of
namespaces it's loading and check if the current is already in the set
then give an error.

However, I don't think clojure supports circular dependency since
loading is sequential. I know there's a trick for functions to be
circularly dependent, and I suppose that could be done with files, but
you'd have to load the files manually, not with (ns).

Unless I'm missing something, this is probably something people will
expect to work, so a friendly error message would be good.

-Mike

On Sep 9, 1:29 am, "ntu...@googlemail.com" <ntu...@googlemail.com>
wrote:

[Brett Morgan]

On Tue, Sep 9, 2008 at 8:12 PM, ntu...@googlemail.com
<ntu...@googlemail.com> wrote:
>
> On Sep 9, 10:51 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
>> Would you kindly educate me in how you believe that Clojure would go
>> about trapping your error and giving you an error message instead of
>> running out of stack space, given that you had given it a
>> non-terminating dependency list?
>
> First please note that circular includes are nothing specific to
> Clojure and other compilers have solved this problem multiple times
> already.

For C, protection against circular dependencies is on the head of the
programmer, in the form of #ifdef guards.

For Java, circular dependency is not an issue, primarily because there
is no macros, and thus an included file cannot be influenced by what
is in the including file.

Clojure has macros...

> Second I am not insisting on a error message. As I said, the precise
> semantics of require can be debated. For instance the ns macro can
> always check a set of declared ns symbols before processing the ns
> declaration further, putting a new ns symbol into this set as soon as
> it is encountered. Wheather it silently stops then or issues an error
> message is up to discussion. Also note that this is not a concrete
> suggestion how to implement the ns macro, it should just illustrate
> that this is not an instance of the halting problem.

I think you will find it is, thanks to the presence of macros.

[Brett Morgan]

On Tue, Sep 9, 2008 at 8:20 PM, Mike Hinchey <hinc...@gmail.com> wrote:
>
> It doesn't seem *impossible* for require and use to keep a var set of
> namespaces it's loading and check if the current is already in the set
> then give an error.

And that technique is itself open to stack overflow attacks. Oh, we
could play this game all night. =)

> However, I don't think clojure supports circular dependency since
> loading is sequential. I know there's a trick for functions to be
> circularly dependent, and I suppose that could be done with files, but
> you'd have to load the files manually, not with (ns).
>
> Unless I'm missing something, this is probably something people will
> expect to work, so a friendly error message would be good.
>
> -Mike
>
> On Sep 9, 1:29 am, "ntu...@googlemail.com" <ntu...@googlemail.com>
> wrote:
>> On Sep 9, 8:48 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
>>
>> > You seem to be asking for the
>> > compiler to be able to prove that your computation finishes, and if it
>> > doesn't then give you a sane response.
>>
>> No.
> >
>

--

Brett Morgan http://brett.morgan.googlepages.com/

[ntu...@googlemail.com]

On Sep 9, 11:28 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:

> On Tue, Sep 9, 2008 at 8:20 PM, Mike Hinchey <hinche...@gmail.com> wrote:
>
> > It doesn't seem *impossible* for require and use to keep a var set of
> > namespaces it's loading and check if the current is already in the set
> > then give an error.
>
> And that technique is itself open to stack overflow attacks. Oh, we
> could play this game all night. =)

Care to give an example of such an "attack"?

[ntu...@googlemail.com]

On Sep 9, 11:26 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
> For C, protection against circular dependencies is on the head of the
> programmer, in the form of #ifdef guards.

There is #import as a GCC extension (also used in Objective-C).

[Brett Morgan]

Anything that fills up the table. And i'm getting messy with my
terminology. JVMs don't have stacks and heaps. Just memory. Too late
at night.

[Brett Morgan]

Which expand out to #ifdef guards, if memory serves.

[Randall R Schulz]

On Tuesday 09 September 2008 01:51, Brett Morgan wrote:
> ...

>
> Would you kindly educate me in how you believe that Clojure would go
> about trapping your error and giving you an error message instead of
> running out of stack space, given that you had given it a
> non-terminating dependency list?

In this case the matter is nothing other than cycle detection in a
graph. It's eminently decidable.

Randall Schulz

[Brett Morgan]

So what do you do about the macros that change the semantics of the
included code between the two inclusions of said code?

>
> Randall Schulz

[Randall R Schulz]

On Tuesday 09 September 2008 07:00, Brett Morgan wrote:

> On Tue, Sep 9, 2008 at 11:58 PM, Randall R Schulz wrote:
> > On Tuesday 09 September 2008 01:51, Brett Morgan wrote:
> >> ...
> >>
> >> Would you kindly educate me in how you believe that Clojure would
> >> go about trapping your error and giving you an error message
> >> instead of running out of stack space, given that you had given it
> >> a non-terminating dependency list?
> >
> > In this case the matter is nothing other than cycle detection in a
> > graph. It's eminently decidable.
>
> So what do you do about the macros that change the semantics of the
> included code between the two inclusions of said code?

Perhaps I missed something, but how does that apply to the case at hand?

Randall Schulz

[Rich Hickey]

It doesn't feel terribly much different to me from:

(defn foo [] (foo))

My point is, having encountered this error (which is not the kind of
thing that is going to lurk around to bite you deep at runtime), was
it not obvious what the problem was? Did Clojure, and the work you
were doing, vanish? It may not have been the one you want, but you got
an error and a place in the code to look.

Certainly there are areas where there could be more explicit messages,
but the detection and reporting of errors has a cost (in time,
sometimes runtime, effort, code size and complexity) and I don't want
to incur that cost unless it is solving a real, common problem, not
just a theoretical one.

Rich

[Dmitri P]

Whatever you do, don't kill Clojure while trying to save us from
ourselves.

[ntu...@googlemail.com]

On Sep 9, 4:26 pm, Rich Hickey <richhic...@gmail.com> wrote:
> My point is, having encountered this error (which is not the kind of
> thing that is going to lurk around to bite you deep at runtime), was
> it not obvious what the problem was? Did Clojure, and the work you
> were doing, vanish? It may not have been the one you want, but you got
> an error and a place in the code to look.

Well, in the example I gave it is relatively easy to see but if your
inclusion cycle is larger and you eventually only get a
StackOverflowException, pointing you to something like
"clojure.lang.Compiler$CompilerException: filename.clj:0: null" it is
far from obvious to see what went wrong. One needs to carefully
examine all inclusions in the whole graph to track down the cycle,
something a machine could do much better.

[ntupel]

On Tue, 2008-09-09 at 23:57 +1000, Brett Morgan wrote:
> On Tue, Sep 9, 2008 at 10:31 PM, ntu...@googlemail.com
> <ntu...@googlemail.com> wrote:
> >
> > On Sep 9, 11:26 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
> >> For C, protection against circular dependencies is on the head of the
> >> programmer, in the form of #ifdef guards.
> >
> > There is #import as a GCC extension (also used in Objective-C).
> >
>
> Which expand out to #ifdef guards, if memory serves.

So what? It just shows you another effective way to tackle the cycle
problem. As a programmer I don't care if I use "include" or "import" or
"require" to load my dependencies. But I do care if I need to make extra
steps to not include stuff twice. I really can not believe that we have
to discuss this age old problem which has been solved so many times
already again and again. This is just plain stupid.

[Brett Morgan]

Well, you could code your own include macro to achieve the affect you
are after. It is an open source project, after all.

[ntupel]

I know and in fact I had my own version of require long before
clojure-contrib was started. But I was glad that it was no longer needed
when clojure-contrib.lib was included because something as basic as this
needs to be part of the standard distribution. And now despite of these
promising developments it seems that I must again come up with a
homegrown solution as I can not convince the Clojure community that it
should be part of Clojure itself. I am delighted!

[ntupel]

On Tue, 2008-09-09 at 07:26 -0700, Rich Hickey wrote:
> Certainly there are areas where there could be more explicit messages,
> but the detection and reporting of errors has a cost (in time,
> sometimes runtime, effort, code size and complexity) and I don't want
> to incur that cost unless it is solving a real, common problem, not
> just a theoretical one.

Just to make myself clear - I clearly said in my first reply to your
post:

"One can argue whether this should result in an error message or
whether the semantics of require are satisfied if the namespaces
are loaded once each."

So I would be glad if the bug is fixed by silently stopping the load if
the namespace is already found in *loaded-libs*. After all the
infrastructure is in place and all that is needed is recording the lib
before the actual load in *loaded-libs* and if the load fails to remove
it again which slightly complicates load-one and/or load-all but still
it seems to be a small price to pay for correctness.

[Rich Hickey]

On Sep 10, 1:38 am, ntupel <ntu...@googlemail.com> wrote:
> On Tue, 2008-09-09 at 23:57 +1000, Brett Morgan wrote:
> > On Tue, Sep 9, 2008 at 10:31 PM, ntu...@googlemail.com
> > <ntu...@googlemail.com> wrote:
>
> > > On Sep 9, 11:26 am, "Brett Morgan" <brett.mor...@gmail.com> wrote:
> > >> For C, protection against circular dependencies is on the head of the
> > >> programmer, in the form of #ifdef guards.
>
> > > There is #import as a GCC extension (also used in Objective-C).
>
> > Which expand out to #ifdef guards, if memory serves.
>
> So what? It just shows you another effective way to tackle the cycle
> problem.

First off, let me say that there's nothing wrong in your asking for
this feature, and I'd like to get this dialogue back on a productive
track.

> As a programmer I don't care if I use "include" or "import" or
> "require" to load my dependencies. But I do care if I need to make extra
> steps to not include stuff twice.

If you don't write any cyclic dependencies there are no extra steps.
This is not about multiple includes, that is already handled.

If you do write cyclic dependencies, there is a bug in your program
logic.

You don't like the way the bug is manifested/reported, point taken.

So far, for me, this seems highly theoretical. If it becomes a common
problem for people, I'll be happy to make an enhancement in this area.

If you don't want to wait, submit a patch (and a CA if you haven't
already), and I'll look at it. I will say that the "silent ignore"
path is not an option - cyclic dependencies are an error you can't
leave in place. There will be other tools that need the dependencies
to be acyclic.

Rich

[Stephen C. Gilardi]

On Sep 10, 2008, at 7:43 AM, Rich Hickey wrote:

> If you don't want to wait, submit a patch (and a CA if you haven't
> already), and I'll look at it. I will say that the "silent ignore"
> path is not an option - cyclic dependencies are an error you can't
> leave in place. There will be other tools that need the dependencies
> to be acyclic.

The enclosed patch modifies "load" to detect and prevent loading a
resource while another load of the same resource is pending in the
same thread. It works at the "load" level using paths so the
protection is comprehensive across load, require, use and ns. It
supports using ":verbose" to see what's going on.

Here's a simple example:

cyclic.clj:

(ns cyclic
(:use cyclic))

user=> (require 'cyclic :verbose)
(clojure/load "/cyclic/cyclic.clj")
(clojure/load "/cyclic/cyclic.clj")
java.lang.Exception: cannot load '/cyclic/cyclic.clj' again while it
is loading
[...]

And an example where mutual.a :uses mutual.b, mutual.b :uses mutual.c,
and mutual.c :uses mutual.a

user=> (require 'mutual.a :verbose)
(clojure/load "/mutual/a/a.clj")
(clojure/load "/mutual/b/b.clj")
(clojure/load "/mutual/c/c.clj")
(clojure/load "/mutual/a/a.clj")
java.lang.Exception: cannot load '/mutual/a/a.clj' again while it is
loading
[...]

--Steve

[ntu...@googlemail.com]

On Sep 10, 4:32 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> The enclosed patch modifies "load" to detect and prevent loading a  
> resource while another load of the same resource is pending in the  
> same thread. It works at the "load" level using paths so the  
> protection is comprehensive across load, require, use and ns. It  
> supports using ":verbose" to see what's going on.

Very nice - thank you very much. I wanted to give it a try this
evening (GMT), but now I don't have to :) I hope this will be
considered for inclusion into Clojure. Thanks again.

[Rich Hickey]

On Sep 10, 10:32 am, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> On Sep 10, 2008, at 7:43 AM, Rich Hickey wrote:
>
> > If you don't want to wait, submit a patch (and a CA if you haven't
> > already), and I'll look at it. I will say that the "silent ignore"
> > path is not an option - cyclic dependencies are an error you can't
> > leave in place. There will be other tools that need the dependencies
> > to be acyclic.
>
> The enclosed patch modifies "load" to detect and prevent loading a
> resource while another load of the same resource is pending in the
> same thread. It works at the "load" level using paths so the
> protection is comprehensive across load, require, use and ns. It
> supports using ":verbose" to see what's going on.
>

Patch applied (rev 1020) - thanks!

Rich