After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 92131 - Recalculating in the wrong order can produce very deep stacks
Recalculating in the wrong order can produce very deep stacks
Status: RESOLVED FIXED
Product: Gnumeric
Classification: Applications
Component: Analytics
git master
Other All
: Normal normal
: ---
Assigned To: Jody Goldberg
Jody Goldberg
: 120787 127202 161335 332479 332698 341675 347341 348903 599799 (view as bug list)
Depends on:
Blocks:
 
 
Reported: 2002-08-30 16:03 UTC by Felipe
Modified: 2013-01-26 17:16 UTC
See Also:
GNOME target: ---
GNOME version: ---

Attachments
Patch to try. (1.17 KB, patch)
2003-07-13 02:03 UTC, Morten Welinder 		needs-work Details | Review
Entirely new patch (7.48 KB, patch)
2003-07-21 19:09 UTC, Morten Welinder 		needs-work Details | Review
append deps (3.20 KB, patch)
2003-08-27 15:28 UTC, Jody Goldberg 		committed Details | Review
Sample gnumeric file (56.87 KB, application/x-gnumeric)
2005-01-21 00:54 UTC, Morten Welinder 		  Details
Back-and-forth traversal of dependency list (5.50 KB, patch)
2009-02-25 15:27 UTC, Morten Welinder 		none Details | Review

Description Felipe 2002-08-30 16:03:48 UTC 
If you drag a cell downwards and the cell contains a formula, Gnumeric
quits with a `Illegal instruction' error.
Comment 1 Morten Welinder 2002-08-30 16:09:45 UTC 
Please supply careful and precise instruction for this.  (Of the kind
"type XYZ into cell A14", ...)

Also, what version?
Comment 2 Felipe 2002-08-30 17:07:32 UTC 
This error happens with any formula in any cell. For instance, typing
`=E2' in E3 and dragging to E30000.
Comment 3 Jody Goldberg 2002-08-30 19:08:09 UTC 
This is somewhat OS specific.
This will not occur in all cases only in the case where you create a very deep
nested expression.  The recalc can then overload the stack on some systems.

By filling from E3 -> E30000 we end up recalculating E30000 first which
requests E29999 ....

30000 is alot of stack frames

I have an idea that might ameliorate the problem in the majority of the cases. 
In the longer term we probably need to manage the stack manually, but that is
tricky in the presence of iterative expressions.
Comment 4 Morten Welinder 2003-01-07 21:00:54 UTC 
This is the current call pattern:

+ Trace 32406

  • #0 gnm_expr_eval
    at expr.c line 678
  • #1 cell_eval_content
    at dependent.c line 1147
  • #2 gnm_expr_eval
    at expr.c line 1009
  • #3 cell_eval_content
    at dependent.c line 1147
  • #4 gnm_expr_eval
    at expr.c line 1009
  • #5 cell_eval_content
    at dependent.c line 1147
  • #6 gnm_expr_eval
    at expr.c line 1009
  • #7 cell_eval_content
    at dependent.c line 1147
  • #8 gnm_expr_eval
    at expr.c line 1009
  • #9 cell_eval_content
    at dependent.c line 1147
  • #10 gnm_expr_eval
    at expr.c line 1009
  • #11 cell_eval_content
    at dependent.c line 1147
  • #12 gnm_expr_eval
    at expr.c line 1009
  • #13 cell_eval_content
    at dependent.c line 1147
  • #14 gnm_expr_eval
    at expr.c line 1009
  • #15 cell_eval_content
    at dependent.c line 1147
  • #16 gnm_expr_eval
    at expr.c line 1009
  • #17 cell_eval_content
    at dependent.c line 1147
  • #18 gnm_expr_eval
    at expr.c line 1009
  • #19 cell_eval_content
    at dependent.c line 1147
  • #20 gnm_expr_eval
    at expr.c line 1009
  • #21 cell_eval_content
    at dependent.c line 1147
  • #22 gnm_expr_eval
    at expr.c line 1009
  • #23 cell_eval_content
    at dependent.c line 1147
  • #24 gnm_expr_eval
    at expr.c line 1009
  • #25 cell_eval_content
    at dependent.c line 1147
  • #26 gnm_expr_eval
    at expr.c line 1009
  • #27 cell_eval_content
    at dependent.c line 1147
  • #28 gnm_expr_eval
    at expr.c line 1009
  • #29 cell_eval_content
    at dependent.c line 1147
  • #30 gnm_expr_eval
    at expr.c line 1009 






Comment 5


Jody Goldberg





          2003-01-08 05:35:05 UTC
        



It can get more ugly in cases with range depends.  The collect functions are
then going be the start of the nesting.  That would make for a significantly
deeper stack.  However, I doubt that is as common a layout as the cellref case.







Comment 6


Morten Welinder





          2003-01-08 16:50:46 UTC
        



A1=1 B1=1
A2=sum(a1:b1)*1 B2=a1

drag A2:B2 down and get a stack like this one...





+
Trace
    32444






    

  • 
#0
gnm_expr_eval

    
                at expr.c
                  line
                  678

    

    • 

  • 
#1
function_iterate_argument_values

    
                at func.c
                  line
                  1203

    

    • 

  • 
#2
collect_floats

    
                at collect.c
                  line
                  167

    

    • 

  • 
#3
float_range_function

    
                at collect.c
                  line
                  240

    

    • 

  • 
#4
gnumeric_sum

    
                at func-builtin.c
                  line
                  53

    

    • 

  • 
#5
function_call_with_list

    
                at func.c
                  line
                  784

    

    • 

  • 
#6
gnm_expr_eval

    
                at expr.c
                  line
                  975

    

    • 

  • 
#7
gnm_expr_eval

    
                at expr.c
                  line
                  776

    

    • 

  • 
#8
cell_eval_content

    
                at dependent.c
                  line
                  1147

    

    • 

  • 
#9
cb_iterate_cellrange

    
                at func.c
                  line
                  1084

    

    • 

  • 
#10
sheet_foreach_cell_in_range

    
                at sheet.c
                  line
                  2258

    

    • 

  • 
#11
workbook_foreach_cell_in_range

    
                at workbook.c
                  line
                  678

    

    • 

  • 
#12
function_iterate_do_value

    
                at func.c
                  line
                  1150

    

    • 

  • 
#13
function_iterate_argument_values

    
                at func.c
                  line
                  1214

    

    • 

  • 
#14
collect_floats

    
                at collect.c
                  line
                  167

    

    • 

  • 
#15
float_range_function

    
                at collect.c
                  line
                  240

    

    • 

  • 
#16
gnumeric_sum

    
                at func-builtin.c
                  line
                  53

    

    • 

  • 
#17
function_call_with_list

    
                at func.c
                  line
                  784

    

    • 

  • 
#18
gnm_expr_eval

    
                at expr.c
                  line
                  975

    

    • 

  • 
#19
gnm_expr_eval

    
                at expr.c
                  line
                  776

    

    • 













Comment 7


Jody Goldberg





          2003-03-17 05:42:47 UTC
        



Leave as a placeholder to get this fixed.






Comment 8


Morten Welinder





          2003-07-13 02:03:31 UTC
        



Created attachment 18250 [details] [review]
Patch to try.






Comment 9


Morten Welinder





          2003-07-13 02:05:34 UTC
        



That patch is untested and needs some configure.in work.  But the basics
should be right.  However, the requested stack size in there is a guess.

The patch expands the stack; a real fix would eliminate the very deep
recursion.







Comment 10


Jody Goldberg





          2003-07-14 23:28:16 UTC
        



As mentioned in irc, the patch and various variants do not play nicely
with pthreads.  Anything linking with gnome-vfs has threading enabled.

We'll need to bite the bullet and do a sort of some form.






Comment 11


Morten Welinder





          2003-07-21 19:09:31 UTC
        



Created attachment 18492 [details] [review]
Entirely new patch






Comment 12


Morten Welinder





          2003-07-21 19:11:44 UTC
        



The above patch handles everything but circular dependencies.

The only suspect areas are
* Handling of names.
* Handling of cell ranges.  This patch will almost want the range
  looking for things that need evaluation.

Even in the presense of such problems, the patch is safe.







Comment 13


Jody Goldberg





          2003-08-27 15:26:48 UTC
        



*** Bug 120787 has been marked as a duplicate of this bug. ***






Comment 14


Jody Goldberg





          2003-08-27 15:28:03 UTC
        



Created attachment 19552 [details] [review]
append deps






Comment 15


Jody Goldberg





          2003-08-27 15:33:04 UTC
        



the proposed patch is dead simple, and does not solve the problem in
all cases.  It only solves it for the case of f(n) = g(f(n-1)) which
seems more common than the converse.

We'll need a better solution during 1.3






Comment 16


Jody Goldberg





          2004-02-18 18:40:57 UTC
        



*** Bug 127202 has been marked as a duplicate of this bug. ***






Comment 17


Jody Goldberg





          2004-08-16 21:52:37 UTC
        



Comment on attachment 18492 [details] [review]
Entirely new patch

One of the big speed wins in 1.2 was the removal of double iterating over
ranges.






Comment 18


Morten Welinder





          2005-01-21 00:54:14 UTC
        



Created attachment 36318 [details]
Sample gnumeric file

This problem is entirely too easy to trigger.  For sample workbook, simply
insert a row before A.






Comment 19


Morten Welinder





          2005-01-21 00:55:15 UTC
        



*** Bug 161335 has been marked as a duplicate of this bug. ***






Comment 20


Morten Welinder





          2005-01-21 00:56:52 UTC
        



Upping priority.






Comment 21


Morten Welinder





          2006-02-27 02:47:00 UTC
        



*** Bug 332479 has been marked as a duplicate of this bug. ***






Comment 22


Morten Welinder





          2006-02-27 02:47:57 UTC
        



*** Bug 332698 has been marked as a duplicate of this bug. ***






Comment 23


Morten Welinder





          2006-07-13 13:27:17 UTC
        



*** Bug 347341 has been marked as a duplicate of this bug. ***






Comment 24


Morten Welinder





          2006-08-01 00:17:37 UTC
        



*** Bug 348903 has been marked as a duplicate of this bug. ***






Comment 25


Morten Welinder





          2006-10-17 14:06:59 UTC
        



1.7.2 contains code to increase the stack size available for this.
That's not a fix, but it should be good enough to handle the most
common cases of this problem.







Comment 26


Jon Kåre Hellan





          2006-10-17 17:43:55 UTC
        



*** Bug 341675 has been marked as a duplicate of this bug. ***






Comment 27


Morten Welinder





          2009-02-25 15:27:09 UTC
        



Created attachment 129492 [details] [review]
Back-and-forth traversal of dependency list

Storing this patch here so it won't get lost.  In practical terms, this solves
the problem except when someone creates a deep cyclic dependency.






Comment 28


Morten Welinder





          2009-10-27 23:09:48 UTC
        



We need a Win32 solution for this.  Something like the code in
gnm_pre_parse_init to increase the stack size.






Comment 30


Morten Welinder





          2009-10-27 23:42:00 UTC
        



...or maybe

http://makesweet.com/bozo/2008/01/16/compiling-ode-with-mingw-on-linux/






Comment 31


Morten Welinder





          2009-10-28 12:53:07 UTC
        



*** Bug 599799 has been marked as a duplicate of this bug. ***






Comment 32


Morten Welinder





          2011-02-26 14:11:52 UTC
        



For the record, this was fixed on win32 a while back by asking for a larger
stack during linking.






Comment 33


Morten Welinder





          2013-01-26 17:16:13 UTC
        



Effectively fixed years ago.