Multiple nested lambda-style are exponentially slow

[SLaks]

This is a followup of #2556.

I ended up needing to pass the @content fake-lambda as a parameter as well.

Now, my LESS hangs when compiled.

I stripped it down to the bare minimum (shown below), and it takes over a minute to compile.

I tried debugging the compiler, and found that env.frames grows to contain thousands of entries, but I'm not sure how to optimize.

Stripped-down source:

.fullAdder(@c, @prefix, @carryIn) {
    @prefixFormat: %(~'#%s-%%s', @prefix);
    .op(@c,
        { .c(@c) { .op(@c, %(@prefixFormat, a), and, %(@prefixFormat, b)) } },
        or,
        { .c(@c) { .op(@c,
            @carryIn,
            and,
            { .c(@c) { .op(@c, %(@prefixFormat, a), xor, %(@prefixFormat, b)); } }
        ); } }
    );
}



.op(
    abc, and, 
    { .c(@c) { .fullAdder(@c, 
        chained-adder-4,
        { .c(@c) { .fullAdder(@c,
            chained-adder-3,
            { .c(@c) { .fullAdder(@c,
                chained-adder-2,
                { .c(@c) { 
                    .op(@c, chained-adder-1-a, and, chained-adder-1-b); 
                } }
            ); } }
        ); } }
    ); } }, {
        color: red;
    }
);






// The .op() mixin calls its @content callback iff the
// specified logical operation evaluates to true.  The
// input parameters (@first and @second) can either be
// selectors to combine (typically :checked selectors)
// or detached rulesets containing further .op() calls
// to chain.
// To pass a .op() call, use the following syntax:
// { .c(@c) { .op(@c, blah, xor, blah); } }
// We need this complexity to pass @invertCombinator &
// @content from the outer call; see 
// https://github.com/less/less.js/issues/2558

// This overload is called by the outermost operation,
// as opposed to operations passed as detached ruleset 
// parameters.  It calls the actual overloads with the
// default !invertCombinator and the explicitly-passed
// @content parameter
.op(@first, @operation, @second, @content) when (@operation = and), (@operation = xor), (@operation = or)  {
    .op(false @content, @first, @operation, @second);   // Pass @content via scope
}

// These overloads are called in detached rulesets when chaining
.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = xor) and not (@invertCombinator) {
    #private.callInverted(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
    #private.call(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
}
.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = xor) and (@invertCombinator) {
    #private.callInverted(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
    #private.call(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
}

.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = or) and not (@invertCombinator) {
    #private.call(~'', @first, @content);
    #private.call(~'', @second, @content);
}
.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = or) and (@invertCombinator) {
    #private.callInverted(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
}

.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = and) and not (@invertCombinator) {
    #private.call(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
}
.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = and) and (@invertCombinator) {
    #private.callInverted(~'', @first, @content);
    #private.callInverted(~'', @second, @content);
}

#private {
    // Calls a selector (as a string or a nested ruleset),
    // inside the context that this selector was called in
    .call(@combinator, @selector, @content) when (isString(@selector)) {
        &@{combinator}@{selector}:checked { @content(); }
    }
    .call(@combinator, @selector, @content) when  (isKeyword(@selector)) {
        &@{combinator}#@{selector}:checked { @content(); }
    }

    .call(@combinator, @selector, @content) when (default()) {  // isruleset(@selector) doesn't work
        &@{combinator} {
            @selector();
            .c(false @content);
        }
    }

    // Same as above, but passes @invertCombinator
    // to invert the result of the combinator.
    .callInverted(@combinator, @selector, @content) when (isString(@selector)) {
        &@{combinator}@{selector}:not(:checked) { @content(); }
    }
    .callInverted(@combinator, @selector, @content) when (isKeyword(@selector)) {
        &@{combinator}#@{selector}:not(:checked) { @content(); }
    }

    .callInverted(@combinator, @selector, @content) when (default()) {  // isruleset(@selector) doesn't work
        &@{combinator} {
            @selector();
            .c(true @content);
        }
    }
}

Removing the six copies of , @content: extract(@c, 2) (which flow the @content through the parameter instead of through scope) makes the compilation time sane, but breaks the output. You can see the current, broken output behavior here (source); it skips the second half of a doubly-nested combinator.

You can see the minimal case that necessitates this fix here.

Any idea how to make this work?

[seven-phases-max]

Hmm, try to use overloading (aka pattern-matching) instead of default parameters, e.g. instead of:

.op(@c, @first, @operation, @second, @invertCombinator: extract(@c, 1), @content: extract(@c, 2)) when (@operation = and) and (@invertCombinator) {
    #private.callInverted(~'', @first, @content);
    #private.callInverted(~'', @second, @content);
}

provide explicit definitions::

.op(@c, @first, @operation, @second) when (@operation = and) {
    .op(@c, @first, extract(@c, 1), extract(@c, 2))
}

.op(@c, @first, @operation, @second, @invertCombinator, @content) 
    when (@operation = and) and (@invertCombinator) {
        #private.callInverted(~'', @first, @content);
        #private.callInverted(~'', @second, @content);
}

[SLaks]

That's a great idea, and makes the code a lot cleaner (.op(@first, xor, @second, invert, @content) { ... }; thanks!), but it doesn't help at all.

I think the problem is that there are too many .c() overloads in scope from calls to different @content()s (especially because, with something closer to my full themed code, I think I saw extra incorrect output that might come from calling the wrong callback).
I'll try adding a constrained parameter to force each call to resolve to only its mixin callback.

[SLaks]

Adding a disambiguator didn't help at all.

The full source for that attempt is

.fullAdder(@c, @id, @prefix, @carryIn) {
    @prefixFormat: %(~'#%s-%%s', @prefix);
    .op(@c, fA1,
        { .c(@c, fA1) { .op(@c, x, %(@prefixFormat, a), and, %(@prefixFormat, b)) } },
        or,
        { .c(@c, fA1) { .op(@c, @id,
            @carryIn,
            and,
            { .c(@c, @innerId) when (@innerId = @id){ .op(@c, x, %(@prefixFormat, a), xor, %(@prefixFormat, b)); } }
        ); } }
    );
}



.op(x1,
    abc, and, 
    { .c(@c, x1) { .fullAdder(@c, x2,
        chained-adder-4,
        { .c(@c, x2) { .fullAdder(@c, x3,
            chained-adder-3,
            { .c(@c, x3) { .fullAdder(@c, x4,
                chained-adder-2,
                { .c(@c, x4) { 
                    .op(@c, x, chained-adder-1-a, and, chained-adder-1-b); 
                } }
            ); } }
        ); } }
    ); } }, {
        color: red;
    }
);






// The .op() mixin calls its @content callback iff the
// specified logical operation evaluates to true.  The
// input parameters (@first and @second) can either be
// selectors to combine (typically :checked selectors)
// or detached rulesets containing further .op() calls
// to chain.
// To pass a .op() call, use the following syntax:
// { .c(@c) { .op(@c, blah, xor, blah); } }
// We need this complexity to pass @invertCombinator &
// @content from the outer call; see 
// https://github.com/less/less.js/issues/2558

// This overload is called by the outermost operation,
// as opposed to operations passed as detached ruleset 
// parameters.  It calls the actual overloads with the
// default !invertCombinator and the explicitly-passed
// @content parameter
.op(@id, @first, @operation, @second, @content) when (@operation = and), (@operation = xor), (@operation = or)  {
    .op(normal @content, @id, @first, @operation, @second);   // Pass @content via scope
}

.op(@c, @id, @first, @operation, @second) when (length(@c) > 1) {
    .op(@first, @operation, @second, extract(@c, 1), extract(@c, 2));
}

// These overloads are called in detached rulesets when chaining
.op(@first, xor, @second, normal, @content) {
    #private.callInverted(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
    #private.call(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
}
.op(@first, xor, @second, invert, @content) {
    #private.callInverted(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
    #private.call(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
}

.op(@first, or, @second, normal, @content) {
    #private.call(~'', @first, @content);
    #private.call(~'', @second, @content);
}
.op(@first, or, @second, invert, @content) {
    #private.callInverted(~'', @first, {
        #private.callInverted(~' ~ ', @second, @content);
    });
}

.op(@first, and, @second, normal, @content) {
    #private.call(~'', @first, {
        #private.call(~' ~ ', @second, @content);
    });
}
.op(@first, and, @second, invert, @content) {
    #private.callInverted(~'', @first, @content);
    #private.callInverted(~'', @second, @content);
}

#private {
    // Calls a selector (as a string or a nested ruleset),
    // inside the context that this selector was called in
    .call(@combinator, @selector, @content) when (isString(@selector)) {
        &@{combinator}@{selector}:checked { @content(); }
    }
    .call(@combinator, @selector, @content) when  (isKeyword(@selector)) {
        &@{combinator}#@{selector}:checked { @content(); }
    }

    .call(@combinator, @selector, @content) when (default()) {  // isruleset(@selector) doesn't work
        &@{combinator} {
            @selector();
            .c(normal @content, @id);
        }
    }

    // Same as above, but passes @invertCombinator
    // to invert the result of the combinator.
    .callInverted(@combinator, @selector, @content) when (isString(@selector)) {
        &@{combinator}@{selector}:not(:checked) { @content(); }
    }
    .callInverted(@combinator, @selector, @content) when (isKeyword(@selector)) {
        &@{combinator}#@{selector}:not(:checked) { @content(); }
    }

    .callInverted(@combinator, @selector, @content) when (default()) {  // isruleset(@selector) doesn't work
        &@{combinator} {
            @selector();
            .c(invert @content, @id);
        }
    }
}

[rjgotten]

The problem is partly in the way mixins are called and the way Less is set up with lazy evaluation.

It creates a plethora of additional environment frames on the frame stack for scope merging, parameter resolution, default parameter values (which can be lazily evaluated expressions that still need expanding), etc.

I sidestep a great deal of this additional weight by using a custom lambda function that binds parameters into detached rulesets and then I execute those bound rulesets. Detached rulesets are much, MUCH more light-weight than full mixins.

While this doesn't solve the problem, it atleast defers it until you reach far greater input sets or far greater recursion depth.

The real underlying problem is that Less is based on a functional model that heavily invites use of tail recursion, yet doesn't implement anything to process said tail recursions efficiently. As soon as you start using recursive constructs, performance goes down the crapper. I'm also not really sure if there's an efficient way to solve this problem generically.