strictFuncs/views design issue

[timotheecour]

strictFuncs/views seems to have a design issue, which prevents algorithm.sorted and many other procs from being func as I noticed when I started investigating the initial CI failures in in #16304 (comment)

What's worse is that, when using generic func's, the issue only manifests itself when the func is instantiated with types containing ref, so that generic code that's seemingly valid when used in some project may fail when used in other contexts, causing regressions when proc's are changed to func's in a seemingly innocuous way (see example 6 for an example of such regression).

Example 1

with --experimental:strictFuncs this gives: Error: 'sortedFake2' can have side effects

  func sortedFake1[T](a: openArray[T]): seq[T] =
    for i in 0 .. a.high: result.add a[i]
  func sortedFake2[T](a: openArray[T]): seq[T] =
    result = newSeq[T](a.len)
    for i in 0 .. a.high: result[i] = a[i]
  type Foo1 = object
  type Foo2 = ref object
  block:
    let a1 = sortedFake1([Foo1()]) # ok
    let a2 = sortedFake1([Foo2()]) # ok
  block:
    let a1 = sortedFake2([Foo1()]) # ok
    let a2 = sortedFake2([Foo2()]) # error: Error: 'sortedFake2' can have side effects

Example 2

after reduction of the CI error I saw in #16304 (comment):

when true: # D20201209T112151:here gitissue
  type Foo = ref object
  proc fnSideEffect(n: Foo) = echo 1
  func aux(b: var Foo, bar: proc (x: Foo)) = discard
  func foo(a: Foo, bar: proc(x: Foo)) =
    bar(a) # ok
    var s = a
    aux(s, bar) # bug: gives error here
  var c = Foo()
  foo(c, fnSideEffect)

Example 3

this works fine, which is a reduction of the example in #16303:

when true:
  type Foo = ref object
  proc fnSideEffect(a: Foo) = echo 1
  func foo(a: Foo, bar: proc(x: Foo)) = bar(a)
  var a = Foo()
  foo(a, fnSideEffect)

Example 4

reduction of Example 2:

when true:
  type Foo = ref object
  func aux(b: var Foo) = discard
  func foo(a: Foo) =
    var s = a
    aux(s)
  foo(Foo())

also gives:

t11479.nim(158, 8) Error: 'foo' can have side effects
an object reachable from 'a' is potentially mutated
t11479.nim(160, 9) the mutation is here
t11479.nim(159, 9) is the statement that connected the mutation to the parameter
    func foo(a: Foo) =

Example 5

shows the kind of regressions you get:
before #16293

nim r --experimental:strictFuncs main # ditto with views
ok

after #16293

nim r --experimental:strictFuncs main # ditto with views
Error: 'zip' can have side effects

when true:
  import std/sequtils
  type Foo = ref object
    x: int
  let a1 = zip(@[1,2], @[1,2]) # ok
  let a2 = zip(@[Foo(x: 1)], @[Foo(x: 2)]) # error

EDIT: likewise with other procs, eg sequtils.map, eg:

when true:
  import std/sequtils
  func tap[T](a: T): T = a
  type Foo = ref object
    x: int
  let b = map([Foo(x: 1), Foo(x: 2)], tap)

Error: 'map' can have side effects
an object reachable from 's' is potentially mutated

Example 6

this valid code stops to work after #16293:

• with --experimental:views, it hits Error: 'zip' can have side effects
• without, it hits: Error: invalid type: 'openArray[int]' for let

when true:
  proc test(x: openArray[int]) =
    let y: openArray[int] = toOpenArray(x, 0, 0)
  import std/sequtils
  type Foo = ref object
    x: int
  let a1 = zip(@[1,2], @[1,2])
  let a2 = zip(@[Foo(x: 1)], @[Foo(x: 2)])

ditto with algorithm.map:

when true:
  {.experimental: "views".}
  import std/sequtils
  func tap[T](a: T): T = a
  type Foo = ref object
    x: int
  proc test[T](x: openArray[T]) =
    let y = toOpenArray(x, 0, 0)
    let y2 = y.map(tap) #  Error: 'map' can have side effects
  test(@[Foo(x: 1), Foo(x: 2)])

Example 7

see #18065 (comment), because of --experimental:strictFuncs, a cast was used:

 {.cast(noSideEffect).}:
    result.mimes = mimes.newOrderedTable()

which is IMO a sign of defeat; and on top of that it masks actual side effects for code not built with --experimental:strictFuncs

Additional Information

• devel 1.5.1 a32acc3
• related to func doesn't check for side effects in proc parameters #16303

[timotheecour]

[moved to top post]

[Araq]

What's worse is that, when using generic func's, the issue only manifests itself when the func is instantiated with types containing ref, so that generic code that's seemingly valid when used in some project may fail when used in other contexts, causing regressions when proc's are changed to func's in a seemingly innocuous way.

This was outlined when we announced strict funcs on the forum, yes. It's well known to me. I don't have a solution beyond making the writetracking smarter.

[timotheecour]

this causes regressions that are hard to fix, see example 6 I just added, which shows valid code that has stopped working after #16293, because --experimental:views is needed but the func change breaks it.

I don't see how this can be fixed with current views design, nor some of the many other issues with --experimental:views; it's only going to get worse because func is viral.

I don't have a solution beyond making the writetracking smarter.

I do have a solution.

I've worked hard on #14976 and IMO we should re-open it, it offers a better and more general approach to safe views/1st class openarray:

• it enabled escape-safe views in a much more general way than offered by --experimental:views, in particular handles ptr, views pointing to inside objects, mutable vs non-mutable views (see extensive tests in https://github.com/nim-lang/Nim/pull/14976/files#diff-effffbdb4da4fa51505f036d8566c32488ed4f342a4100c8ededfcfb5d5dee8a, eg and mview vs view), views arising from variables not arising from input parameters

(whereas --experimental:views doesn't support most of these and can't work with mutable openarray views for example, refs #15745)

• it doesn't have any of the restrictive limitations (eg must borrow from the first parameter), instead relies on interprocedural analysis (robust to however generics are instantiated etc)
• it's actually a simpler approach than --experimental:views in the sense that all it does is determine whether code is escape-safe or not (all done in 1 place, not spread throughout compiler code), and unlike --experimental:views (see openArray views in VM and js give errors #16306 for views+js or vm) has 0 impact on codegen / backend specificities; safe mutable/immutable views can instead simply be defined in library code (and be safe).

I've done more work on that branch to fix remaining edge cases for detection of escapes but these haven't been pushed as the PR was closed.

extensions of interprocedural analysis from #14976

memory tracking in that PR could be adapted/generalized to other problems eg sideEffect tracking but that's a separate issue from what's needed for escape safe views, whereas, as shown in this issue, --experimental:views is impacted by this (#16305) bug.

Example:

• tracking ROM memory to avoid writes, solving Writing to readonly data gives SIGBUS error; should be CT error instead #8463
• tracking memory aliasing, enabling automatic inference of {.noalias.}
• tracking immutable data, enabling let a {.immutable.} = expr
• tracking whether a {.NotNil.} variable was initialized in a more robust way than current approach

and for all these, giving warning/error when compiler cannot prove that these guarantees don't hold

[Araq]

instead relies on interprocedural analysis (robust to however generics are instantiated etc)

Interprocedural analysis is a dead-end. Been there, done that, error messages are not understandable and tend to point into code that you didn't write yourself. Interprocedural analysis is the opposite of "robust", it's fragile by construction.

in particular handles ptr, views pointing to inside object

That's a huge design problem. It means that some usages of ptr are proven for you by the compiler but not others and there is no visual clue when what is done.

Also, you don't even have an RFC for your work.

[ee7]

Should we revert some generic proc -> func changes before the Nim 1.6.0 release?

My understanding is that upgrading Nim 1.4.x to 1.6.0 RC2 breaks code that:

• uses --experimental:strictFuncs
• and uses stdlib generic procs that were changed to funcs
• which are instantiated with a type containing ref

as seen in e.g. @timotheecour's example 5:

{.experimental: "strictFuncs".}
import std/sequtils
type Foo = ref object
  x: int
let a1 = zip(@[1,2], @[1,2]) # ok
let a2 = zip(@[Foo(x: 1)], @[Foo(x: 2)]) # error in 1.6.0 RC2, but not 1.4.x

Or do we consider this error when using an "experimental" feature as sufficiently minor/obscure to be acceptable, and that we should just wait until the strictFuncs implementation doesn't produce an error for this case?

[ee7]

I opened #18998 to workaround the rest of the strictFuncs regressions in sequtils, finding all the problematic func and reverting them back to proc for now.

Aside from the already mentioned zip, the same issue occured with unzip and repeat.

@Araq wrote:

can we look into why the compiler still doesn't understand repeat and friends.

There was previously a reduction in this post, but I've moved it to #20863.

[Araq]

Resolved by #21066