kevinlawler / kona

Open-source implementation of the K programming language
ISC License
1.36k stars 138 forks source link

Heisenbug? Problem disappears when you add output. #621

Closed gitonthescene closed 2 years ago

gitonthescene commented 2 years ago

More working on AoC problems. I'm sorry that I haven't narrowed this down yet, but I thought it best to post first and ask questions later. Here's the code:

data:(0$')'"\n"\1_"
5483143223
2745854711
5264556173
6141336146
6357385478
4167524645
2176841721
6882881134
4846848554
5283751526"
ix:{x,/:\:y}.(!:'^data)
n:-1+^data
lm:9
f9:{,/{y,/:&lm=x}.'+(x;!#x)}
nb:{{x+!(1+y-x)}.'0|(n&(-1 1;-1 1)+x)}
sd:{x@&:(#y)=y?/:x}
nxt:{(,/.[ix;y])@&,/lm=.[1+x;y]}
fl:{{pts:nb[*z];(.[x;pts;+;1];(y,,*z);1_ z,sd[nxt[x;pts];y,z])}.(x)}
st:{{r:{#*|x}(fl)/(1+x;!0;f9@1+x);rr[&:lm<rr:,/*r]:0;((^x)#rr;y+#r@1)}.(x)}

The function st runs just fine the first time but doesn't the second:

  1(st)/(data;0)
((7 7 0 6 3 6 5 4 4 4
  4 0 7 8 0 7 6 0 4 3
  7 4 8 6 7 7 8 5 0 7
  7 3 7 4 6 5 8 5 0 0
  7 6 0 0 8 0 7 7 0 0
  5 5 0 0 0 7 7 8 7 8
  5 7 0 0 0 0 4 8 3 2
  0 0 0 0 0 0 6 3 4 5
  8 0 0 0 0 0 0 7 6 5
  7 6 0 0 0 0 5 7 3 7)
 35)
  2(st)/(data;0)
(((;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;))
 36)

Attempting to investigate, the problem disappears:

  2{{w:&:lm<rr:,/*r:{#*|x}(fl)/(1+x;!0;f9@1+x);((^x)#@[rr;w;:;0];y+#r@1)}.(x)}/(data;0)
(((;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;)
  (;;;;;;;;;))
 36)
  2{`0:"\n",,/$:'(,/*x);{w:&:lm<rr:,/*r:{#*|x}(fl)/(1+x;!0;f9@1+x);((^x)#@[rr;w;:;0];y+#r@1)}.(x)}/(data;0)

5483143223274585471152645561736141336146635738547841675246452176841721688288113448468485545283751526
7706365444407807604374867785077374658500760080770055000778785700004832000000634580000007657600005737((0 0 5 0 8 0 0 7 5 5
  7 5 0 0 8 0 0 5 6 4
  8 8 0 0 0 0 0 0 3 8
  8 6 0 0 0 0 0 0 4 1
  8 8 3 5 0 8 0 0 6 3
  6 6 1 2 3 0 0 0 0 0
  6 8 1 1 2 5 0 0 0 8
  2 2 1 1 1 3 0 0 0 0
  0 4 2 1 1 2 5 0 0 0
  0 0 2 1 1 1 8 0 0 0)
 80)

My gut says this is something to do with the local variables getting reused on each iteration rather than starting fresh, but that's just a complete guess. In any event having output is having an effect it shouldn't.

gitonthescene commented 2 years ago

Also, the same thing does not happen in tio which I believe is running an older version of kona.

[EDIT]: FWIW, this solves the problem on tio. I.e. I found my bug, but had to debug on tio. This code has a similar problem to the above in the current kona.

gitonthescene commented 2 years ago

FWIW, this also feels like a memory error to me.

gitonthescene commented 2 years ago

I ran git bisect on these changes and the last output that matches the good output from 2019-01-17 is the following:

$ git bisect good; make; ./k bug.k
4466f8671dac81d7773cc95764741bcae4df6667 is the first bad commit
commit 4466f8671dac81d7773cc95764741bcae4df6667
Author: tavmem <tavmem@gmail.com>
Date:   Thu Apr 4 21:04:21 2019 -0400

    adjustments to sd() ... show details

 src/k.c  |  2 +-
 src/kx.c | 20 ++++++++------------
 2 files changed, 9 insertions(+), 13 deletions(-)
make: Nothing to be done for `all'.
kona      \ for help. \\ to exit.

  ((0 3 9 7 6 6 6 8 6 6
  0 7 4 9 7 6 6 9 1 8
  0 0 5 3 9 7 6 9 3 3
  0 0 0 4 2 9 7 8 2 2
  0 0 0 4 2 2 9 8 9 2
  0 0 5 3 2 2 2 8 7 7
  0 5 3 2 2 2 2 9 6 6
  9 3 2 2 2 2 8 9 6 6
  7 9 2 2 2 8 6 8 6 6
  6 7 8 9 9 9 8 7 6 6)
 1656
 100)
((0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0)
 3125
 195)
 $

It looks like the output changed at this rev, but it's not necessarily wrong at that rev. Also the error at HEAD with the attached script is a 'type error. When I bisect, I run into a 'wsfull and a `'value' error along the way. If I accept the changed output mentioned above, the first error comes at the following:

$ git bisect good; make; ./k bug.k
1f02a068912106f8f1f8cc14e0914aceb911877e is the first bad commit
commit 1f02a068912106f8f1f8cc14e0914aceb911877e
Author: Tom Szczesny <tom@new-host-2.home>
Date:   Wed May 15 16:19:57 2019 -0400

    pass dict by value

 src/kx.c |  2 +-
 src/kx.h |  2 +-
 src/p.c  | 26 +++++++++++++-------------
 src/p.h  |  4 ++--
 src/v.c  |  2 +-
 src/v.h  |  2 +-
 6 files changed, 19 insertions(+), 19 deletions(-)
make: Nothing to be done for `all'.
kona      \ for help. \\ to exit.

  [(0 3 9 7 6 6 6 8 6 6
  0 7 4 9 7 6 6 9 1 8
  0 0 5 3 9 7 6 9 3 3
  0 0 0 4 2 9 7 8 2 2
  0 0 0 4 2 2 9 8 9 2
  0 0 5 3 2 2 2 8 7 7
  0 5 3 2 2 2 2 9 6 6
  9 3 2 2 2 2 8 9 6 6
  7 9 2 2 2 8 6 8 6 6
  6 7 8 9 9 9 8 7 6 6);1656;100]
[(0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0
  0 0 0 0 0 0 0 0 0 0);3125;195]
$

I've attached the file I used to bisect. (suffix changed) bug.k.txt