chaining of procs with concepts yields Error: too nested for type matching or exponential compile time

[timotheecour]

EDIT previous title was: blocker for implementing D ranges in Nim: Error: too nested for type matching but I found a proper workaround in #9422 (comment) ; turns out this issue was with chaining of concepts.

/cc @zah @Araq @LemonBoy

motivation

I'm trying to bring to Nim the concept of D ranges (https://dlang.org/phobos/std_range.html and http://ddili.org/ders/d.en/ranges.html), arguably one of the most powerful and unique features of D. One feature of D ranges is that they have no compiler support (beyond foreach syntax sugar) and are purely defined in library code, which makes me think we should be able to do the same in Nim.

Why should we care ? because Nim's iterators have serious shortcomings, as has been discussed many times (see also related github issues):

• inline iterators are fast but aren't first class citizens (making composition hard for example, but many other limitations)
• closure iterators are a bit more flexible but much less efficient (I measured a 10X speed slowdown here: def-/nim-iterutils@29ec94c)

Unlike Nim closure iterators, D ranges are a zero-cost abstraction (as fast as manual code could be), while being first class citizens, meaning you can return ranges, combine them arbitrarily, etc. They're also more flexible than even closure iterators, eg can be extended with arbitrary concepts via duck-typing: D's standard library defines (and uses extensively) variations on Ranges such as:

• InputRange (most similar to Nim iterators)
• ForwardRange (can be saved)
• BidirectionalRange (can be iterated in either direction)
• RandomAccessRange (ranges with len and random access; act similar to a seq but they don't have to be backed by in-memory buffer, eg: iota: see https://dlang.org/library/std/range/iota.html)

implementation

My implementation below is very straightfoward and works... to a point. I define below map, filter, take (that operate lazily on ranges, returning ranges), as well as a simplified version of D's iota range (https://dlang.org/library/std/range/iota.html) which is a lazy range with elements 0 through n-1.

This works well:

## defines `iota` range
type
  Iota = object
    n:int
    i:int
proc notEmpty(a:Iota):bool=a.i < a.n
proc popFront(a:var Iota)=a.i.inc
proc front(a:Iota):auto=a.i

## example usage
var b2=Iota(n:100).
    map((x:int) => x*2).
    take(5)
# no allocation until this point: everything is done lazily, returning a range

echo b2.toArray # prints: `@[0, 2, 4, 6, 8]`

the bug

but whenever I have a composition of >=3 range operations (instead of just 2, like above), I get a giant error with 13145 lines of compiler error mentioning "too nested for type matching" in a lot of places; see also WORKAROUND below (with its associated caveat)

full implementation

(EDIT extracted from nimble package drange that I'm working on: https://github.com/timotheecour/vitanim/tree/master/drange)

See fully self contained example below where I show the bug I'm running into.

type 
  isInputRange* = concept x
    x.notEmpty is bool
    not(x.front is void)
    # TODO
    # x.popFront() is void
    x.popFront

## map
type 
  MapObj*[R:isInputRange, Fun]=object
    r:R
    fun:Fun

  isMapObj* = concept a
    a is MapObj[a.R, a.Fun]

proc map*[R, Fun](r:R, fun:Fun):auto = MapObj[R,Fun](r:r, fun:fun)

template notEmpty*(a:isMapObj):bool = a.r.notEmpty
template popFront*(a:var isMapObj) = a.r.popFront
template front*(a:isMapObj):auto = a.fun(a.r.front)

## filter
type 
  FilterObj*[R:isInputRange, Fun]=object
    r:R
    fun:Fun
    primed:bool

  isFilterObj* = concept a
    a is FilterObj[a.R, a.Fun]

proc filter*[R, Fun](r:R, fun:Fun):auto = FilterObj[R,Fun](r:r, fun:fun, primed:false)

template prime*(a:var isFilterObj):void =
  if a.primed.not:
    while a.r.notEmpty and a.fun(a.r.front).not:
      a.r.popFront
    a.primed=true

template notEmpty*(a:var isFilterObj):bool = 
  a.prime
  a.r.notEmpty

template popFront*(a:var isFilterObj) =
  while true:
    a.r.popFront
    if a.r.notEmpty.not or a.fun(a.r.front):
      break
  a.primed=true

template front*(a:var isFilterObj):auto =
  a.prime
  a.r.front

## take
type 
  TakeObj*[R:isInputRange]=object
    r:R
    n:int
    count:int

  isTakeObj* = concept a
    a is TakeObj[a.R]

proc take*[R](r:R, n:int):auto = TakeObj[R](r:r, n:n, count:0)

template notEmpty*(a:isTakeObj):bool = a.count < a.n and a.r.notEmpty

template popFront*(a:var isTakeObj) =
  a.r.popFront
  a.count.inc

template front*(a:var isTakeObj):auto = a.r.front

template toArray*(a:isInputRange):auto=
  type E=a.front.type
  var ret:seq[E]
  while a.notEmpty:
    ret &= a.front
    a.popFront
  ret



## iota range
type
  Iota = object
    n:int
    i:int

proc notEmpty(a:Iota):bool=a.i < a.n
proc popFront(a:var Iota)=a.i.inc
proc front(a:Iota):auto=a.i

#[
D20181018T010031:here BUG:
]#
proc test()=
  var b2=Iota(n:100).
    # comment any of these and it'll work; with all 3, it gives 13145 lines of error
    map(proc(x:int): auto = x*2).
    map(proc(x:int): auto = x*3).
    take(5)

  echo b2.toArray

test()

related forum discussion with @Araq

• https://gitter.im/nim-lang/Nim?at=5bc3d17564cfc273f9c99bf0

links

• http://ddili.org/ders/d.en/ranges.html
• https://dlang.org/library/std/range/iota.html
• https://wiki.dlang.org/Component_programming_with_ranges
• https://dlang.org/phobos/std_range.html

workaround (with exponential compile time)

EDIT as a workaround, set if prevMatchedConcept.depth > 10 in sigmatch.nim ; however this results in dramatic (exponential in number of chained ranges) slowdown with deeper expression, as shown in timotheecour/vitanim@e92cdaf :

1 chained map: 1 seconds
2 chained map: 2 seconds
3 chained map: 10 seconds
4 chained map: 107 seconds

[timotheecour]

fixed ! see timotheecour/vitanim@3885dd5

instead of using concepts (a: isMapObj), I'm now using the types directly (a: MapObj)

I'll leave this issue open, it looks odd that concepts used this way lead to either Error: too nested for type matching or exponential compilation times, but at least it's not blocking D range implementation in Nim anymore !

[Araq]

The exponential compiletimes for concepts are known and mysterious. :-) But I'm leaving this open since it's a new test case that doesn't depend on converter as the previous snippets did.