Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JS codegen can produce extreme switch statements with case a of range #8821

Closed
skilchen opened this issue Aug 30, 2018 · 13 comments · Fixed by #20548
Closed

JS codegen can produce extreme switch statements with case a of range #8821

skilchen opened this issue Aug 30, 2018 · 13 comments · Fixed by #20548

Comments

@skilchen
Copy link
Contributor

then try to compile the following silly int32 tester for the js backend:

# isInt32.nim
proc isInt32(i: int): bool =
  case i 
  of low(int32)..high(int32):
    return true
  else:
    return false

echo isInt32(1)

Unless you have lots and lots of memory and disk space, running nim js isInt32.nim will make your system unusable. So if you are adventurous enough to try it, save all relevant work before the experiment. Most likely you will have to perform a hard reset...
Nim should refuse to compile harmless looking stupidities like this one. For this code on the js backend Nim tries to produce a switch statement with 4294967295 case labels. This is a little bit too much ...

@Araq
Copy link
Member

Araq commented Aug 30, 2018

The C codegen deals with this appropriately. :-)

@timotheecour
Copy link
Member

Nim should refuse to compile harmless looking stupidities like this one

a more robust approach: setting limit on process memory usage (not GC memory as it doesn't cover everything), eg on linux ulimit -m

  • on linux this should be settable via a C api and called by Nim compiler
  • what about OSX and windows?

@dom96
Copy link
Contributor

dom96 commented Sep 3, 2018

Unless you have lots and lots of memory and disk space, running nim js isInt32.nim will make your system unusable.

Nim should refuse to compile harmless looking stupidities like this one.

Yes, but your system also shouldn't die when a rogue process attempts to allocate too much memory.

@Araq Araq changed the title are you looking for a way to bring your system down using Nim? JS codegen can produce extreme switch statements Jan 13, 2019
@stale
Copy link

stale bot commented Aug 4, 2020

This issue has been automatically marked as stale because it has not had recent activity. If you think it is still a valid issue, write a comment below; otherwise it will be closed. Thank you for your contributions.

@stale stale bot added the stale Staled PR/issues; remove the label after fixing them label Aug 4, 2020
ringabout added a commit to ringabout/Nim that referenced this issue Nov 1, 2020
@Araq Araq closed this as completed in 544cb10 Nov 2, 2020
@Clyybber Clyybber removed the stale Staled PR/issues; remove the label after fixing them label Nov 2, 2020
@timotheecour
Copy link
Member

timotheecour commented Nov 2, 2020

@xflywind the proper fix should be to handle
case x of 1 .. 65536: similarly to C codegen, without generating code bloat, eg transforming it to:
if x >= 1 and x <= 65536: and then jsgen this (or directly jsgen it with those semantics)

#15809 just patches around the problem, and still generates inefficient code (with code bloat)

@ringabout
Copy link
Member

I have considered this solution but a bit hard. Nim compiler outputs JS code by concatating strings. If stmt should be put in the default branch and in the front of the origin parts.

@timotheecour
Copy link
Member

timotheecour commented Nov 2, 2020

@xflywind

I have considered this solution but a bit hard. Nim compiler outputs JS code by concatating strings. If stmt should be put in the default branch and in the front of the origin parts.

you can take a look at compiler/transf.nim which is an alternative to adding more logic to jsgen (either should work):

# This module implements the transformator. It transforms the syntax tree
# to ease the work of the code generators. Does some transformations:
#
# * inlines iterators

narimiran pushed a commit that referenced this issue Nov 5, 2020
(cherry picked from commit 544cb10)
@timotheecour
Copy link
Member

timotheecour commented Nov 18, 2020

this issue wasn't properly fixed, I'm re-opening.
This:

proc main(a: char) =
  case a
  of 'a'..'z', 'A'..'Z': echo "alpha"
  of '0'..'9': echo "digit"
  else: echo "other"
main('x')

produces exhaustive switch statements (even if V8 were to optimize it, you'd be left with code that can't be minified).

And in other cases with more switch items, the compiler would bail out.

And the recommendation of using <= instead of case in code doesn't work in practice, as stdlib or 3rd party libraries, that use the typical switch case would not work (or be inefficient) with js backend.

unction main_687865857(a_687865859) {
  var F={procname:"t11311.main",prev:framePtr,filename:"/Users/timothee/git_clone/nim/timn/tests/nim/all/t11311.nim",line:0};
  framePtr = F;
    F.line = 6;
    switch (a_687865859) {
    case 97:
    case 98:
    case 99:
    case 100:
    case 101:
    case 102:
    case 103:
    case 104:
    case 105:
    case 106:
    case 107:
    case 108:
... skipping for brevity
    case 83:
    case 84:
    case 85:
    case 86:
    case 87:
    case 88:
    case 89:
    case 90:
      F.line = 7;
      rawEcho(makeNimstrLit("alpha"));
      break;
    case 48:
    case 49:
    case 50:
    case 51:
    case 52:
    case 53:
    case 54:
    case 55:
    case 56:
    case 57:
      F.line = 8;
      rawEcho(makeNimstrLit("digit"));
      break;
    default: 
      F.line = 9;
      rawEcho(makeNimstrLit("other"));
      break;
    }
  framePtr = F.prev;

  
}

proposal

Instead, jsgen should simply produce code that transforms of case 'a'..'z, 'A'..'Z' into something similar to

if a >= 'a' and a <= 'z' or a >= 'A' and a <= 'Z'

(and that transformation could be done in transf.nim before reaching jsgen as mentioned in #8821 (comment))

@timotheecour timotheecour reopened this Nov 18, 2020
@timotheecour timotheecour changed the title JS codegen can produce extreme switch statements JS codegen can produce extreme switch statements with case a of range Nov 18, 2020
@ringabout ringabout self-assigned this Nov 19, 2020
@ringabout ringabout mentioned this issue Nov 20, 2020
PMunch pushed a commit to PMunch/Nim that referenced this issue Jan 6, 2021
mildred pushed a commit to mildred/Nim that referenced this issue Jan 11, 2021
@timotheecour
Copy link
Member

timotheecour commented Feb 13, 2021

workaround: library defined case, refs nim-lang/RFCs#332 (comment)

import macros
macro `case`*(a: string, branches: varargs[untyped]) = ...
case x:
of 10..13: ...
else: ...

but this would require some import std/jscase

@ringabout ringabout removed their assignment Feb 19, 2021
irdassis pushed a commit to irdassis/Nim that referenced this issue Mar 16, 2021
ardek66 pushed a commit to ardek66/Nim that referenced this issue Mar 26, 2021
@ringabout
Copy link
Member

I made a patch at jsgen(when the number of branchs exceeds 1000, compiler generates if else statement

function isInt32_452984833(i_452984834) {
    var Temporary1;

  var result_452984835 = false;

  BeforeRet: do {
    Temporary1 = i_452984834;    if (((Temporary1 >= -2147483648) & (Temporary1 <= 2147483647))) {
    result_452984835 = true;
    break BeforeRet;
    }
    else {
    result_452984835 = false;
    break BeforeRet;
    }
    
  } while (false);

  return result_452984835;

}

@timotheecour
Copy link
Member

I made a patch at jsgen(when the number of branchs exceeds 1000, compiler generates if else statement

sounds good, do you have a WIP PR?
why 1000 instead of always transforming consecutive ranges case x of 10..20 into corresponding if x >= x1 and x <= x2 ?

@ringabout
Copy link
Member

ringabout commented Aug 16, 2021

My wip PR is here, I'm still experimenting it

https://github.com/xflywind/Nim/tree/pr_js

@bung87
Copy link
Collaborator

bung87 commented Sep 14, 2022

@timotheecour I've done transformed for float range, it seems to me only string, bool, enum need switch , others should transform as well ?

bung87 added a commit to bung87/Nim that referenced this issue Oct 12, 2022
Araq pushed a commit that referenced this issue Oct 14, 2022
#20548)

* fix #8821 JS codegen can produce extreme switch statements with case a of range

* remove totalRange
capocasa pushed a commit to capocasa/Nim that referenced this issue Mar 31, 2023
…th case … (nim-lang#20548)

* fix nim-lang#8821 JS codegen can produce extreme switch statements with case a of range

* remove totalRange
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment