search

SomMeri / less4j

Less language is an extension of css and less4j compiles it into regular css. Less adds several dynamic features into css: variables, expressions, nested rules, and so on. Less was designed to be compatible with css and any correct css file is also correct less file.
145 stars 47 forks source link

detect mixin infinite loop. Issues 160, 239 #290

Closed NcIgor closed 9 years ago

NcIgor commented 9 years ago

Hi SomMeri

I propose my variant of detecting infinite loops in mixins. This problem was descibed in issues 160 and 239.

InfiniteLoopDetector tries to find similar stack trace for current position. I added 2 constans: DEEP_OF_STACK - number of equal parent elements MIN_LOOP_COUNT - number of similar loops

For some projects which generate static css such detector is not required. And I think it could be possible to make it optional through Less Configuration

SomMeri commented 9 years ago

Thank you, I did not had time to fully read your solution yet, but I definitely will.

SomMeri commented 9 years ago

Direct link to #160 and #239

andrey-nc commented 9 years ago

Also waiting for this change. Thanks Igor!

SomMeri commented 9 years ago

I pulled your changes into NcIgor-master branch, so you can see how I merged it. Sorry it took me so much time to respond.

My problem with the algorithm is that it ignores state of variables and ends up cutting too much. It may prevent intentional loops - a mixin being called ten times may mean that someone is building a grid of 10 columns or something like that (bootstrap does that).

The simplest example where it happens is this: 

//looping case
.spanX (@index) when (@index > 0) {
  loop: member @index;
  .spanX((@index - 1));
}
.spanX (@index) when (@index =< 0) { 
  loop: end;
}

#loop-here {
 .spanX(15);
}

The unfortunate thing is that since called mixin sees literally everything caller see (e.g. all variables and mixins including those in parents ), it is hard to detect when variables/mixins state repeats (without going through whole scope tree which would be very time consuming). E.g. it is not enough to compare values of mixin parameters.

The other (minor and probably solvable) issue is that scope.getOwner().toString() is not a good way to distinguish scopes because toString method prints whatever is practical during debugging and has no special contract :(. I think that this could be replaced by something similar so it is just a small thing.

I like the idea of looking at the scope itself you use in that pull request. It does not depend on mixin evaluation algorithm which makes it less fragile. This seems more like a way to go which is why it took me more time to answer - the way it is done is promising although implementation cuts too much.

Maybe less4j could have a debug mode which would return warnings on suspicious loops - people could turn it on when they would be getting stack overflow (maybe with DEEP_OF_STACK and MIN_LOOP_COUNT configurable or at least higher). Or it could be used quick check when scope becomes suspiciously big and be followed by more sophisticated algorithm if returns true.

Edit: The general problem of looping detection is Turing complete which means we wont achieve perfect solution, only some trade off.

NcIgor commented 9 years ago

Thank you for your response

Detecting infinite loop in source code is difficult task especially when code allows 'while' and 'for' loops

Unfortunately when less4j faces with code with infinite loop he continue generate new thread for each "new" mixin. It is makes unnecessary problems with server resources (memory, threads). For us it is very important, such as we allow modify less files online :( For our projects we can ignore issue with that you provide above. It is more importance save server's resource.

1st my implementation to stop generation bad less code was stopping the main less compiler's thread after some times from start (with java.util.concurrent.ExecutorService.shutdownNow()). But it was unsuccessful because less4j doesn't have any condition to stop its work. I think it would be good to have possibility to stop thread for generation styles. It is easy and safe extension.

According to my solution with checking stack trace. toString() method is not the best my idea - it was experimental solution. I tried to make minor changes in existing code. Need to add equals method to Scope class.

Also in my code the method getBodyOwnerParent() is bad. I don't have any idea to change/optimize it.

Also I am going to add infinite loop detector to configurations to have possibility disable it if something goes wrong :)

SomMeri commented 9 years ago

Thank you for adding details, I now understand your use case better. I opened new issue for it #292 - mostly because it is clearer what is needed and the task is slightly different.

I will look around whether there are standard solutions for this "stop thread if needed" or "limit resource" problem - less4j should be single threaded.

SomMeri commented 9 years ago

@NcIgor I think I could add thread interrupted check into mixin calls:

if (Thread.currentThread().isInterrupted())
 throw new Less4jException("thread interrupted");

You could then open compiler in new thread and call its interrupt method when it runs too long. It wont tell you which mixin loops and why, but it would be easy fix that should allow you to kill long running compilation before it consumes too much resources.

Would that work for you?

NcIgor commented 9 years ago

Thank you very much

It would be enough for me now and very useful feature for less4j library in general

SomMeri commented 9 years ago

@NcIgor I added thread interrupt condition. As I needed to test it too, I pushed also TimeoutedLessCompiler implementation of LessCompiler interface which creates time restricted less compiler.