dependent.c 27.8 KB
Newer Older
Arturo Espinosa's avatar
Arturo Espinosa committed
1 2 3
/*
 * eval.c:  Cell recomputation routines.
 *
Michael Meeks's avatar
Michael Meeks committed
4 5
 * Please do not commit to this module, send a patch to Michael.
 *
6 7
 * Authors:
 *  Michael Meeks   (mmeeks@gnu.org)
Michael Meeks's avatar
Michael Meeks committed
8
 *  Miguel de Icaza (miguel@gnu.org)
Arturo Espinosa's avatar
Arturo Espinosa committed
9 10 11 12 13
 */

#include <config.h>
#include <gnome.h>
#include "gnumeric.h"
14
#include "parse-util.h"
15
#include "ranges.h"
16
#include "eval.h"
17
#include "value.h"
18
#include "rendered-value.h"
19
#include "main.h"
20
#include "workbook.h"
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

typedef enum {
	REMOVE_DEPS = 0,
	ADD_DEPS = 1
} DepOperation;

/*
 * A DependencyRange defines a range of cells whose values
 * are used by another Cell in the spreadsheet.
 *
 * A change in those cells will trigger a recomputation on the
 * cells listed in cell_list.
 */
typedef struct {
	/*
	 *  This range specifies uniquely the position of the
	 * cells that are depended on by the cell_list.
	 */
	Range  range;

	/* The list of cells that depend on this range */
	GList *cell_list;
} DependencyRange;

/*
 *  A DependencySingle stores a list of cells that depend
47
 * on the cell at @pos in @cell_list. NB. the EvalPos
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
 * is quite vital since there may not be a cell there yet.
 */
typedef struct {
	/*
	 * The position of a cell
	 */
	CellPos pos;
	/*
	 * The list of cells that depend on this cell
	 */
	GList  *cell_list;
} DependencySingle;

struct _DependencyData {
	/*
	 *   Large ranges hashed on 'range' to accelerate duplicate
	 * culling. This is tranversed by g_hash_table_foreach mostly.
	 */
	GHashTable *range_hash;
	/*
68
	 *   Single ranges, this maps an EvalPos * to a GList of its
69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
	 * dependencies.
	 */
	GHashTable *single_hash;
};

/*
 * Comparission function for the dependency hash table
 */
static gint
range_equal_func (gconstpointer v, gconstpointer v2)
{
	const DependencyRange *r1 = (const DependencyRange *) v;
	const DependencyRange *r2 = (const DependencyRange *) v2;

	if (r1->range.start.col != r2->range.start.col)
		return 0;
	if (r1->range.start.row != r2->range.start.row)
		return 0;
	if (r1->range.end.col != r2->range.end.col)
		return 0;
	if (r1->range.end.row != r2->range.end.row)
		return 0;

	return 1;
}

/*
 * Hash function for DependencyRange structures
 */
static guint
range_hash_func (gconstpointer v)
{
	const DependencyRange *r = v;

	return ((((r->range.start.row << 8) + r->range.end.row) << 8) +
		(r->range.start.col << 8) + (r->range.end.col));
}

static guint
dependency_single_hash (gconstpointer key)
{
	const DependencySingle *d = (const DependencySingle *) key;

	return (d->pos.row << 8) ^ d->pos.col;
}

static gint
dependency_single_equal (gconstpointer ai, gconstpointer bi)
{
	const DependencySingle *a = (const DependencySingle *)ai;
	const DependencySingle *b = (const DependencySingle *)bi;

	return (a->pos.row == b->pos.row &&
		a->pos.col == b->pos.col);
}

DependencyData *
dependency_data_new (void)
{
	DependencyData *deps  = g_new (DependencyData, 1);

	deps->range_hash  = g_hash_table_new (range_hash_func,
					      range_equal_func);
	deps->single_hash = g_hash_table_new (dependency_single_hash,
					      dependency_single_equal);

	return deps;
}
137

138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
static gboolean
dependency_range_destroy (gpointer key, gpointer value, gpointer closure)
{
	DependencyRange *deprange = value;

	g_list_free (deprange->cell_list);
	deprange->cell_list = NULL;

	g_free (value);

	return TRUE;
}

static gboolean
dependency_single_destroy (gpointer key, gpointer value, gpointer closure)
153
{
154 155 156 157 158 159 160 161
	DependencySingle *single = value;

	g_list_free (single->cell_list);
	single->cell_list = NULL;

	g_free (value);

	return TRUE;
162 163
}

164
typedef struct {
165
	ExprRewriteInfo const *rwinfo;
166 167 168 169

	GSList          *cell_list;
} destroy_closure_t;

170
static void
171
cb_range_hash_to_list (gpointer key, gpointer value, gpointer closure)
172
{
173 174 175
	destroy_closure_t *c = closure;
	GList             *l;
	DependencyRange   *dep = value;
176

177 178
	for (l = dep->cell_list; l; l = l->next) {
		Cell *cell = l->data;
179

180 181
		if      (c->rwinfo->type == EXPR_REWRITE_SHEET &&
			 cell->sheet != c->rwinfo->u.sheet)
182

183
			c->cell_list = g_slist_prepend (c->cell_list, l->data);
184

185 186
		else if (c->rwinfo->type == EXPR_REWRITE_WORKBOOK &&
			 cell->sheet->workbook != c->rwinfo->u.workbook)
187

188 189 190
			c->cell_list = g_slist_prepend (c->cell_list, l->data);
	}
}
191

192 193 194 195 196 197 198 199 200 201 202 203 204 205
static void
cb_single_hash_to_list (gpointer key, gpointer value, gpointer closure)
{
	destroy_closure_t *c = closure;
	GList             *l;
	DependencySingle  *dep = value;

	for (l = dep->cell_list; l; l = l->next) {
		Cell *cell = l->data;

		if      (c->rwinfo->type == EXPR_REWRITE_SHEET &&
			 cell->sheet != c->rwinfo->u.sheet)

			c->cell_list = g_slist_prepend (c->cell_list, l->data);
206

207 208 209 210
		else if (c->rwinfo->type == EXPR_REWRITE_WORKBOOK &&
			 cell->sheet->workbook != c->rwinfo->u.workbook)

			c->cell_list = g_slist_prepend (c->cell_list, l->data);
211 212 213
	}
}

214
static void
215
invalidate_refs (Cell *cell, const ExprRewriteInfo *rwinfo)
216 217 218 219 220 221 222 223 224 225 226
{
	ExprTree *newtree;

	newtree = expr_rewrite (cell->u.expression, rwinfo);

	/*
	 * We are told this cell depends on this region, hence if
	 * newtree is null then either we did not depend on it
	 * ( ie. serious breakage ) or we had a duplicate reference
	 * and we have already removed it.
	 */
227
	g_return_if_fail (newtree != NULL);
228

229 230 231 232 233 234 235 236 237 238
#if 0
	fprintf (stderr, "Invalidating to #REF! in %s!%s %p\n",
	cell->sheet->name_quoted, cell_name (cell), newtree);
#endif

	/*
	 * Explicitly do not check for array subdivision, we may be replacing
	 * the corner of an array.
	 */
	cell_set_expr_unsafe (cell, newtree, NULL);
239 240
}

241 242 243 244 245
/*
 * do_deps_destroy :
 * Invalidate references of all kinds to the target region described by
 * @rwinfo.
 */
246
static void
247
do_deps_destroy (Sheet *sheet, const ExprRewriteInfo *rwinfo)
248
{
249 250
	DependencyData   *deps;
	destroy_closure_t c;
251

252 253 254 255 256 257
	g_return_if_fail (sheet != NULL);

	deps = sheet->deps;
	if (deps == NULL)
		return;

258 259 260
	c.rwinfo    = rwinfo;
	c.cell_list = NULL;

261
	if (deps->range_hash) {
262 263
		g_hash_table_foreach (deps->range_hash,
				      &cb_range_hash_to_list, &c);
264

265 266 267
		while (c.cell_list) {
			invalidate_refs (c.cell_list->data, rwinfo);
			c.cell_list = g_slist_remove (c.cell_list, c.cell_list->data);
268
		}
269

270 271 272
		g_hash_table_foreach_remove (deps->range_hash,
					     dependency_range_destroy,
					     NULL);
273 274

		g_hash_table_destroy (deps->range_hash);
275
		deps->range_hash = NULL;
276
	}
277

278
	c.cell_list = NULL;
279
	if (deps->single_hash) {
280 281
		g_hash_table_foreach (deps->single_hash,
				      &cb_single_hash_to_list, &c);
282

283 284 285 286 287 288 289 290
		while (c.cell_list) {
			invalidate_refs (c.cell_list->data, rwinfo);
			c.cell_list = g_slist_remove (c.cell_list, c.cell_list->data);
		}

		g_hash_table_foreach_remove (deps->single_hash,
					     dependency_single_destroy,
					     NULL);
291

292 293
		g_hash_table_destroy (deps->single_hash);
		deps->single_hash = NULL;
294
	}
295 296

	g_free (deps);
297 298 299 300 301 302 303 304 305 306 307 308
	sheet->deps = NULL;
}

void
sheet_deps_destroy (Sheet *sheet)
{
	ExprRewriteInfo rwinfo;

	g_return_if_fail (sheet != NULL);

	rwinfo.type = EXPR_REWRITE_SHEET;
	rwinfo.u.sheet = sheet;
309

310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
	do_deps_destroy (sheet, &rwinfo);
}

void
workbook_deps_destroy (Workbook *wb)
{
	GList          *sheets, *l;
	ExprRewriteInfo rwinfo;

	g_return_if_fail (wb != NULL);

	rwinfo.type = EXPR_REWRITE_WORKBOOK;
	rwinfo.u.workbook = wb;

	sheets = workbook_sheets (wb);
	for (l = sheets; l; l = l->next)
		do_deps_destroy (l->data, &rwinfo);

	g_list_free (sheets);
329 330 331 332 333
}

/**
 * cell_eval_content:
 * @cell: the cell to evaluate.
334
 *
Michael Meeks's avatar
Michael Meeks committed
335 336 337
 * This function evaluates the contents of the cell,
 * it should not be used by anyone. It is an internal
 * function.
338
 *
339
 **/
340
void
341
cell_eval_content (Cell *cell)
Arturo Espinosa's avatar
Arturo Espinosa committed
342
{
343
	Value           *v;
344
	EvalPos	 pos;
Arturo Espinosa's avatar
Arturo Espinosa committed
345

346
	if (!cell_has_expr (cell))
347 348
		return;

349
#ifdef DEBUG_EVALUATION
350
	if (dependency_debugging > 1) {
351
		ParsePos pp;
352

353
		char *exprtxt = expr_decode_tree
354
			(cell->u.expression, parse_pos_init_cell (&pp, cell));
355
		printf ("Evaluating %s: %s ->\n", cell_name (cell), exprtxt);
356 357 358 359
		g_free (exprtxt);
	}
#endif

360
	v = eval_expr (eval_pos_init_cell (&pos, cell),
361
		       cell->u.expression, EVAL_STRICT);
Arturo Espinosa's avatar
Arturo Espinosa committed
362

363
#ifdef DEBUG_EVALUATION
364
	if (dependency_debugging > 1) {
365 366 367
		char *valtxt = v
			? value_get_as_string (v)
			: g_strdup ("NULL");
368
		printf ("Evaluating %s: -> %s\n", cell_name (cell), valtxt);
369 370 371 372
		g_free (valtxt);
	}
#endif

373
	if (v == NULL)
374
		v = value_new_error (&pos, "Internal error");
375

376 377 378
	cell_assign_value (cell, v, NULL);
	rendered_value_calc_size (cell);
	sheet_redraw_cell (cell);
Arturo Espinosa's avatar
Arturo Espinosa committed
379 380
}

381 382 383 384 385 386 387
void
cell_eval (Cell *cell)
{
	g_return_if_fail (cell != NULL);

	if (cell->generation == cell->sheet->workbook->generation)
		return;
Jody Goldberg's avatar
Jody Goldberg committed
388

389 390
	cell->generation = cell->sheet->workbook->generation;

391
	if (cell_has_expr (cell)) {
392
		GList *deps, *l;
393

394
		cell_eval_content (cell);
395

396
		deps = cell_get_dependencies (cell);
Jody Goldberg's avatar
Jody Goldberg committed
397

398
		for (l = deps; l; l = l->next) {
399
			Cell *one_cell = l->data;
400

401
			if (one_cell->generation != cell->sheet->workbook->generation)
Jody Goldberg's avatar
Jody Goldberg committed
402
				eval_queue_cell (one_cell);
403 404 405 406 407
		}
		g_list_free (deps);
	}
}

408
static void
409
add_cell_range_dep (DependencyData *deps, Cell *cell,
410
		    const DependencyRange      *range)
411 412
{
	/* Look it up */
413 414
	DependencyRange *result = g_hash_table_lookup (deps->range_hash, range);

415
	if (result) {
416
		/* Is the cell already listed? */
417
		const GList *cl = g_list_find (result->cell_list, cell);
Arturo Espinosa's avatar
Arturo Espinosa committed
418
		if (cl)
419 420 421 422
			return;

		/* It was not: add it */
		result->cell_list = g_list_prepend (result->cell_list, cell);
423

424 425 426
		return;
	}

427
	/* Create a new DependencyRange structure */
428
	result = g_new (DependencyRange, 1);
429
	*result = *range;
Arturo Espinosa's avatar
Arturo Espinosa committed
430
	result->cell_list = g_list_prepend (NULL, cell);
431

432
	g_hash_table_insert (deps->range_hash, result, result);
433 434
}

435 436 437 438 439
static void
drop_cell_range_dep (DependencyData *deps, Cell *cell,
		     const DependencyRange *const range)
{
	/* Look it up */
440 441 442 443 444 445
	DependencyRange *result;

	if (!deps)
		return;

	result = g_hash_table_lookup (deps->range_hash, range);
446 447 448

#ifdef DEBUG_EVALUATION
	if (dependency_debugging > 0) {
449
		const Range *r = &(range->range);
450
		printf ("Dropping range deps of %s ", cell_name (cell));
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479
		printf ("on range %s%d:",
			col_name (r->start.col),
			r->start.row + 1);
		printf ("%s%d\n",
			col_name (r->end.col),
			r->end.row + 1);
	}
#endif

	if (result) {
		GList *cl = g_list_find (result->cell_list, cell);

		if (!cl) {
/*			g_warning ("Range referenced twice + by some other cells"); */
			return;
		}

		result->cell_list = g_list_remove_link (result->cell_list, cl);
		g_list_free_1 (cl);

		if (!result->cell_list) {
			g_hash_table_remove (deps->range_hash, result);
			g_free (result);
		}
	} else
/*		g_warning ("Unusual; range referenced twice in same formula")*/;
}

static void
480 481
dependency_range_ctor (DependencyRange *range, const Cell *cell,
		       const CellRef   *a,  const CellRef *b)
482
{
483
	CellPos pos;
484

485 486
	pos.col = cell->col_info->pos;
	pos.row = cell->row_info->pos;
487

488 489 490 491 492 493 494
	cell_get_abs_col_row (a, &pos,
			      &range->range.start.col,
			      &range->range.start.row);
	cell_get_abs_col_row (b, &pos,
			      &range->range.end.col,
			      &range->range.end.row);
	range_normalize (&range->range);
495

496
	range->cell_list = NULL;
497 498
	if (b->sheet && a->sheet != b->sheet)
		g_warning ("FIXME: 3D references need work");
499
}
500

501 502 503 504
static void
handle_cell_single_dep (Cell *cell, const CellRef *a,
			DepOperation operation)
{
505
	DependencyData   *deps;
506 507 508 509
	DependencySingle *single;
	DependencySingle  lookup;
	CellPos           pos;

510 511 512 513 514
	if (a->sheet == NULL)
		deps = cell->sheet->deps;
	else
		deps = a->sheet->deps;

515 516
	if (!deps)
		return;
517 518 519

	pos.col = cell->col_info->pos;
	pos.row = cell->row_info->pos;
520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554
	/* Convert to absolute cordinates */
	cell_get_abs_col_row (a, &pos, &lookup.pos.col, &lookup.pos.row);

	single = g_hash_table_lookup (deps->single_hash, &lookup);

	if (operation == ADD_DEPS) {
		if (single) {
			if (!g_list_find (single->cell_list, cell))
				single->cell_list = g_list_prepend (single->cell_list,
								    cell);
			else
				/* Referenced twice in the same formula */;
		} else {
			single  = g_new (DependencySingle, 1);
			*single = lookup;
			single->cell_list = g_list_prepend (NULL, cell);
			g_hash_table_insert (deps->single_hash, single, single);
		}
	} else { /* Remove */
		if (single) {
			GList *l = g_list_find (single->cell_list, cell);

			if (l) {
				single->cell_list = g_list_remove_link (single->cell_list, l);
				g_list_free_1 (l);

				if (!single->cell_list) {
					g_hash_table_remove (deps->single_hash, single);
					g_free (single);
				}
			} else
				/* Referenced twice in the same formula */;
		} else
			/* Referenced twice and list killed already */;
	}
555 556
}

557 558 559 560
/*
 * We add the dependency of Cell a in the ranges
 * enclose by CellRef a and CellRef b
 *
561
 * We compute the location from cell->row_info->pos and cell->col_info->pos
562 563
 */
static void
564 565
handle_cell_range_deps (Cell *cell, const CellRef *a, const CellRef *b,
			DepOperation operation)
566 567
{
	DependencyRange range;
568
	gboolean        single = (a == b);
569

570
	if (single) /* Single, simple range */
571 572 573

		handle_cell_single_dep (cell, a, operation);

574 575
	else {      /* Large range */
		DependencyData *depsa, *depsb;
576

577
		dependency_range_ctor (&range, cell, a, b);
578 579

		depsa = eval_sheet (a->sheet, cell->sheet)->deps;
580
		if (operation)
581
			add_cell_range_dep  (depsa, cell, &range);
582
		else
583 584 585 586 587 588 589 590 591 592 593
			drop_cell_range_dep (depsa, cell, &range);

		depsb = eval_sheet (b->sheet, cell->sheet)->deps;
		if (depsa != depsb) {
			/* FIXME: we need to iterate sheets between to be correct */
			if (operation)
				add_cell_range_dep  (depsb, cell, &range);
			else
				drop_cell_range_dep (depsb, cell, &range);
		}

594
	}
595 596
}

597 598 599 600
/*
 * Adds the dependencies for a Value
 */
static void
601
handle_value_deps (Cell *cell, const Value *value, DepOperation operation)
602
{
603
	switch (value->type) {
604
	case VALUE_EMPTY:
605 606 607
	case VALUE_STRING:
	case VALUE_INTEGER:
	case VALUE_FLOAT:
608 609
	case VALUE_BOOLEAN:
	case VALUE_ERROR:
610 611
		/* Constants are no dependencies */
		break;
612

613
		/* Check every element of the array */
614
		/* FIXME: currently array's only hold alphanumerics */
615
	case VALUE_ARRAY:
616
	{
617
		int x, y;
618

619 620
		for (x = 0; x < value->v_array.x; x++)
			for (y = 0; y < value->v_array.y; y++)
621
				handle_value_deps (cell,
622
						   value->v_array.vals [x] [y],
623
						   operation);
624
		break;
625
	}
626
	case VALUE_CELLRANGE:
627
		handle_cell_range_deps (
Arturo Espinosa's avatar
Arturo Espinosa committed
628
			cell,
629 630
			&value->v_range.cell.a,
			&value->v_range.cell.b,
631
			operation);
632
		break;
633 634 635
	default:
		g_warning ("Unknown Value type, dependencies lost");
		break;
636 637 638 639 640 641 642 643
	}
}

/*
 * This routine walks the expression tree looking for cell references
 * and cell range references.
 */
static void
644
handle_tree_deps (Cell *cell, ExprTree *tree, DepOperation operation)
645
{
Arturo Espinosa's avatar
Arturo Espinosa committed
646
	GList *l;
647

648
	switch (tree->any.oper) {
Morten Welinder's avatar
Morten Welinder committed
649
	case OPER_ANY_BINARY:
650 651
		handle_tree_deps (cell, tree->binary.value_a, operation);
		handle_tree_deps (cell, tree->binary.value_b, operation);
652 653
		return;

Morten Welinder's avatar
Morten Welinder committed
654
	case OPER_ANY_UNARY:
655
		handle_tree_deps (cell, tree->unary.value, operation);
Morten Welinder's avatar
Morten Welinder committed
656
		return;
657 658

	case OPER_VAR:
659
		handle_cell_range_deps (
660
			cell,
661 662
			&tree->var.ref,
			&tree->var.ref,
663
			operation);
664 665
		return;

666
	case OPER_CONSTANT:
667
		handle_value_deps (cell, tree->constant.value, operation);
668
		return;
Jody Goldberg's avatar
Jody Goldberg committed
669

670 671 672 673
	/*
	 * FIXME: needs to be taught implicit intersection +
	 * more cunning handling of argument type matching.
	 */
674
	case OPER_FUNCALL:
675
		for (l = tree->func.arg_list; l; l = l->next)
676
			handle_tree_deps (cell, l->data, operation);
677 678
		return;

679
	case OPER_NAME:
680
		if (tree->name.name->builtin) {
681 682
			/* FIXME: insufficiently flexible dependancy code (?) */
		} else
683
			handle_tree_deps (cell, tree->name.name->t.expr_tree, operation);
684 685
		return;

686
	case OPER_ARRAY:
687
		if (tree->array.x != 0 || tree->array.y != 0) {
688
			/* Non-corner cells depend on the corner */
689 690 691 692
			CellRef a;

			a.col_relative = a.row_relative = 0;
			a.sheet = cell->sheet;
693 694
			a.col   = cell->col_info->pos - tree->array.x;
			a.row   = cell->row_info->pos - tree->array.y;
695 696

			handle_cell_range_deps (cell, &a, &a, operation);
697 698
		} else
			/* Corner cell depends on the contents of the expr */
699
			handle_tree_deps (cell, tree->array.corner.func.expr,
700
					  operation);
701
		return;
702 703 704
	default:
		g_warning ("Unknown Operation type, dependencies lost");
		break;
705
	}
706 707
}

708 709
/**
 * cell_add_dependencies:
710 711
 * @cell:
 *
712 713 714
 * This registers the dependencies for this cell
 * by scanning all of the references made in the
 * parsed expression.
715
 *
716
 **/
717
void
Arturo Espinosa's avatar
Arturo Espinosa committed
718
cell_add_dependencies (Cell *cell)
719 720
{
	g_return_if_fail (cell != NULL);
721
	g_return_if_fail (cell->sheet != NULL);
722
	g_return_if_fail (cell->sheet->deps != NULL);
Morten Welinder's avatar
Morten Welinder committed
723

724 725
	if (cell_has_expr (cell))
		handle_tree_deps (cell, cell->u.expression, ADD_DEPS);
726 727
}

728 729 730 731 732 733 734
/*
 * Add a dependency on a CellRef iff the cell is not already dependent on the
 * cellref.
 *
 * @cell : The cell which will depend on.
 * @ref  : The row/col of the cell in the same sheet as cell to depend on.
 */
Jody Goldberg's avatar
Jody Goldberg committed
735
void
736
cell_add_explicit_dependency (Cell *cell, const CellRef *ref)
Jody Goldberg's avatar
Jody Goldberg committed
737
{
Morten Welinder's avatar
Morten Welinder committed
738 739 740 741 742
	static int warned;
	if (!warned) {
		g_warning ("Redundant cell_add_explicit_dependency function hacked");
		warned = 1;
	}
743 744
}

745 746
/**
 * cell_drop_dependencies:
747 748
 * @cell:
 *
Jody Goldberg's avatar
Jody Goldberg committed
749
 * Remove the Cell from the DependencyRange hash tables
750
 **/
751 752 753 754
void
cell_drop_dependencies (Cell *cell)
{
	g_return_if_fail (cell != NULL);
755
	g_return_if_fail (cell->sheet != NULL);
756

757 758
	if (cell_has_expr (cell))
		handle_tree_deps (cell, cell->u.expression, REMOVE_DEPS);
759 760 761
}

typedef struct {
762
	int   col, row;
763 764
	Sheet *sheet;
	GList *list;
765
} get_cell_dep_closure_t;
766 767

static void
768
search_cell_deps (gpointer key, gpointer value, gpointer closure)
769
{
770 771 772
	DependencyRange *deprange = key;
	Range *range = &(deprange->range);
	get_cell_dep_closure_t *c = closure;
Arturo Espinosa's avatar
Arturo Espinosa committed
773
	GList *l;
774

775
	/* No intersection is the common case */
776
	if (!range_contains (range, c->col, c->row))
777
		return;
778

779
	for (l = deprange->cell_list; l; l = l->next) {
Arturo Espinosa's avatar
Arturo Espinosa committed
780 781
		Cell *cell = l->data;

782
		c->list = g_list_prepend (c->list, cell);
Arturo Espinosa's avatar
Arturo Espinosa committed
783
	}
784 785 786 787 788
#ifdef DEBUG_EVALUATION
	if (dependency_debugging > 1) {
		printf ("Adding list: [\n");
		for (l = deprange->cell_list; l; l = l->next) {
			Cell *cell = l->data;
789 790

			printf (" %s(%d), ", cell_name (cell),
791 792 793 794 795
				cell->generation);
		}
		printf ("]\n");
	}
#endif
796 797
}

798
static GList *
799
cell_get_range_dependencies (const Cell *cell)
800
{
801
	get_cell_dep_closure_t closure;
802

803
	g_return_val_if_fail (cell != NULL, NULL);
804 805 806

	if (!cell->sheet->deps)
		return NULL;
807

808 809
	closure.col   = cell->col_info->pos;
	closure.row   = cell->row_info->pos;
810 811
	closure.sheet = cell->sheet;
	closure.list  = NULL;
812

813 814
	g_hash_table_foreach (cell->sheet->deps->range_hash,
			      &search_cell_deps, &closure);
815 816 817 818

	return closure.list;
}

819 820
static GList *
get_single_dependencies (Sheet *sheet, int col, int row)
821
{
822 823
	DependencySingle  lookup, *single;
	DependencyData  *deps = sheet->deps;
Jody Goldberg's avatar
Jody Goldberg committed
824

825
	g_return_val_if_fail (deps != NULL, NULL);
826

827 828
	lookup.pos.col = col;
	lookup.pos.row = row;
Jody Goldberg's avatar
Jody Goldberg committed
829

830
	single = g_hash_table_lookup (deps->single_hash, &lookup);
831

832
#ifdef DEBUG_EVALUATION
833 834 835 836
	if (dependency_debugging > 0 && single) {
		GList *l = single->cell_list;

		printf ("Single dependencies on %s %d\n",
837
			cell_coord_name (col, row), g_list_length (l));
838 839 840

		while (l) {
			Cell *dep_cell = l->data;
841
			printf ("%s\n", cell_name (dep_cell));
842 843
			l = g_list_next (l);
		}
844 845
	}
#endif
846 847 848 849 850

	if (single)
		return g_list_copy (single->cell_list);
	else
		return NULL;
851 852
}

853
GList *
854
cell_get_dependencies (const Cell *cell)
855
{
856
	GList *deps;
Jody Goldberg's avatar
Jody Goldberg committed
857

858 859 860
	if (!cell->sheet->deps)
		return NULL;

861 862
	deps = g_list_concat (cell_get_range_dependencies (cell),
			      get_single_dependencies (cell->sheet,
863 864
						       cell->col_info->pos,
						       cell->row_info->pos));
865 866 867 868
#ifdef DEBUG_EVALUATION
	if (dependency_debugging > 1) {
		printf ("There are %d dependencies for %s!%s\n",
			g_list_length (deps), cell->sheet->name,
869
			cell_name (cell));
870
	}
871
#endif
872

873
	return deps;
874 875
}

876
/*
Jody Goldberg's avatar
Jody Goldberg committed
877
 * eval_queue_cell:
878 879 880 881
 * @cell: the cell that contains the formula that must be recomputed
 *
 * Queues the cell @cell for recalculation.
 */
Arturo Espinosa's avatar
Arturo Espinosa committed
882
void
Jody Goldberg's avatar
Jody Goldberg committed
883
eval_queue_cell (Cell *cell)
Arturo Espinosa's avatar
Arturo Espinosa committed
884 885 886 887
{
	Workbook *wb;

	g_return_if_fail (cell != NULL);
888

889
	if (cell->cell_flags & CELL_QUEUED_FOR_RECALC)
Morten Welinder's avatar
Morten Welinder committed
890 891
		return;

892
#ifdef DEBUG_EVALUATION
893
	if (dependency_debugging > 2)
894
		printf ("Queuing: %s\n", cell_name (cell));
895
#endif
896
	wb = cell->sheet->workbook;
Arturo Espinosa's avatar
Arturo Espinosa committed
897
	wb->eval_queue = g_list_prepend (wb->eval_queue, cell);
898
	cell->cell_flags |= CELL_QUEUED_FOR_RECALC;
899 900 901
}

/*
Jody Goldberg's avatar
Jody Goldberg committed
902
 * eval_unqueue_cell:
903 904 905 906 907 908 909
 * @cell: the cell to remove from the recomputation queue
 *
 * Removes a cell that has been previously added to the recomputation
 * queue.  Used internally when a cell that was queued no longer contains
 * a formula.
 */
void
Jody Goldberg's avatar
Jody Goldberg committed
910
eval_unqueue_cell (Cell *cell)
911 912
{
	Workbook *wb;
913

914 915
	g_return_if_fail (cell != NULL);

916
	if (!(cell->cell_flags & CELL_QUEUED_FOR_RECALC))
917 918
		return;

919
	wb = cell->sheet->workbook;
920
	wb->eval_queue = g_list_remove (wb->eval_queue, cell);
921
	cell->cell_flags &= ~CELL_QUEUED_FOR_RECALC;
Arturo Espinosa's avatar
Arturo Espinosa committed
922 923 924
}

void
Jody Goldberg's avatar
Jody Goldberg committed
925
eval_queue_list (GList *list, gboolean freelist)
Arturo Espinosa's avatar
Arturo Espinosa committed
926
{
Morten Welinder's avatar
Morten Welinder committed
927
	GList *list0 = list;
928
	Workbook *wb;
Arturo Espinosa's avatar
Arturo Espinosa committed
929

930 931 932
	while (list) {
		Cell *cell = list->data;
		list = list->next;
Morten Welinder's avatar
Morten Welinder committed
933

934
		if (cell->cell_flags & CELL_QUEUED_FOR_RECALC)
Morten Welinder's avatar
Morten Welinder committed
935 936
			continue;

937
#ifdef DEBUG_EVALUATION
938
		if (dependency_debugging > 2)
939
			printf ("Queuing: %s\n", cell_name (cell));
940
#endif
941 942
		/*
		 * Use the wb associated with the current cell in case we have
943 944 945
		 * cross workbook depends
		 */
		wb = cell->sheet->workbook;
Morten Welinder's avatar
Morten Welinder committed
946 947
		wb->eval_queue = g_list_prepend (wb->eval_queue, cell);

948
		cell->cell_flags |= CELL_QUEUED_FOR_RECALC;
949
	}
Morten Welinder's avatar
Morten Welinder committed
950

951 952
	if (freelist)
		g_list_free (list0);
Arturo Espinosa's avatar
Arturo Espinosa committed
953 954
}

Jody Goldberg's avatar
Jody Goldberg committed
955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984
/*
 * eval_unqueue_sheet: Remove all cells from the specified sheet
 *    from the recalc queue.
 *
 * @sheet : the sheet whose cells need to be unqueued.
 */
void
eval_unqueue_sheet (Sheet *sheet)
{
	GList *ptr, *next, *queue;
	Workbook *wb;

	g_return_if_fail (sheet != NULL);
	g_return_if_fail (IS_SHEET (sheet));

	wb = sheet->workbook;
	queue = wb->eval_queue;
	for (ptr = queue; ptr != NULL ; ptr = next) {
		Cell *cell = ptr->data;
		next = ptr->next;

		if (cell->sheet == sheet) {
			cell->cell_flags &= ~CELL_QUEUED_FOR_RECALC;
			queue = g_list_remove_link (queue, ptr);
			g_list_free_1 (ptr);
		}
	}
	wb->eval_queue = queue;
}

Arturo Espinosa's avatar
Arturo Espinosa committed
985 986
static Cell *
pick_next_cell_from_queue (Workbook *wb)
987
{
Arturo Espinosa's avatar
Arturo Espinosa committed
988 989 990 991
	Cell *cell;

	if (!wb->eval_queue)
		return NULL;
992

Arturo Espinosa's avatar
Arturo Espinosa committed
993 994
	cell = wb->eval_queue->data;
	wb->eval_queue = g_list_remove (wb->eval_queue, cell);
995
	if (!(cell->cell_flags & CELL_QUEUED_FOR_RECALC))
996
		printf ("De-queued cell here\n");
997
	cell->cell_flags &= ~CELL_QUEUED_FOR_RECALC;
Arturo Espinosa's avatar
Arturo Espinosa committed
998 999 1000
	return cell;
}

1001 1002 1003 1004
/*
 * Increments the generation.  Every time the generation is
 * about to wrap around, we reset all of the cell counters to zero
 */
Jody Goldberg's avatar
Jody Goldberg committed
1005
static void
1006 1007
workbook_next_generation (Workbook *wb)
{
1008
	if (wb->generation == 255) {
1009
		GList *cell_list = wb->formula_cell_list;
1010

1011
		for (; cell_list; cell_list = cell_list->next) {
1012 1013 1014 1015 1016 1017 1018 1019 1020
			Cell *cell = cell_list->data;

			cell->generation = 0;
		}
		wb->generation = 1;
	} else
		wb->generation++;
}

1021 1022 1023 1024
/*
 * Computes all of the cells pending computation and
 * any dependency.
 */
Arturo Espinosa's avatar
Arturo Espinosa committed
1025 1026 1027
void
workbook_recalc (Workbook *wb)
{
1028
	int generation;
Arturo Espinosa's avatar
Arturo Espinosa committed
1029
	Cell *cell;
1030 1031 1032

	workbook_next_generation (wb);
	generation = wb->generation;
Arturo Espinosa's avatar
Arturo Espinosa committed
1033

1034
	while ((cell = pick_next_cell_from_queue (wb))) {
1035 1036 1037
		if (cell->generation == generation)
			continue;

Arturo Espinosa's avatar
Arturo Espinosa committed
1038 1039
		cell_eval (cell);
	}
1040
}
1041 1042 1043 1044 1045 1046 1047

/*
 * Recomputes all of the formulas.
 */
void
workbook_recalc_all (Workbook *workbook)
{
Jody Goldberg's avatar
Jody Goldberg committed
1048
	eval_queue_list (workbook->formula_cell_list, FALSE);
1049 1050
	workbook_recalc (workbook);
}
1051 1052 1053 1054 1055 1056 1057

static void
dump_cell_list (GList *l)
{
	printf ("(");
	for (; l; l = l->next) {
		Cell *cell = l->data;
1058
		printf ("%s!%s, ", cell->sheet->name_unquoted,
1059
			cell_name (cell));
1060 1061 1062 1063 1064 1065 1066
	}
	printf (")\n");
}

static void
dump_range_dep (gpointer key, gpointer value, gpointer closure)
{
1067 1068
	const DependencyRange *deprange = key;
	const Range *range = &(deprange->range);
1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084

	/* 2 calls to col_name.  It uses a static buffer */
	printf ("\t%s%d:",
		col_name (range->start.col), range->start.row + 1);
	printf ("%s%d -> ",
		col_name (range->end.col), range->end.row + 1);

	dump_cell_list (deprange->cell_list);
}

static void
dump_single_dep (gpointer key, gpointer value, gpointer closure)
{
	DependencySingle *dep = key;

	/* 2 calls to col_name.  It uses a static buffer */
1085
	printf ("\t%s -> ", cell_pos_name (&dep->pos));
1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103

	dump_cell_list (dep->cell_list);
}

void
sheet_dump_dependencies (const Sheet *sheet)
{
	DependencyData *deps;

	g_return_if_fail (sheet != NULL);

	deps = sheet->deps;

	if (deps) {
		printf ("For %s:%s\n",
			sheet->workbook->filename
			?  sheet->workbook->filename
			: "(no name)",
1104
			sheet->name_unquoted);
1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126

		if (g_hash_table_size (deps->range_hash) > 0) {
			printf ("Range hash size %d: range over which cells in list depend\n",
				g_hash_table_size (deps->range_hash));
			g_hash_table_foreach (deps->range_hash,
					      dump_range_dep, NULL);
		}

		if (g_hash_table_size (deps->single_hash) > 0) {
			printf ("Single hash size %d: cell on which list of cells depend\n",
				g_hash_table_size (deps->single_hash));
			g_hash_table_foreach (deps->single_hash,
					      dump_single_dep, NULL);
		}
	}

	if (sheet->workbook->eval_queue) {
		GList *l = sheet->workbook->eval_queue;

		printf ("Unevaluated cells on queue:\n");
		while (l) {
			Cell *cell = l->data;
1127
			printf ("%s!%s\n", cell->sheet->name_unquoted,
1128
				cell_name (cell));
1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148
			l = l->next;
		}
	}
}

typedef struct {
	Range r;
	GList *list;
} get_range_dep_closure_t;

static void
search_range_deps (gpointer key, gpointer value, gpointer closure)
{
	DependencyRange *deprange  =  key;
	Range           *range     = &(deprange->range);
	get_range_dep_closure_t *c =  closure;

	if (!range_overlap (range, &c->r))
		return;

1149
	c->list = g_list_concat (c->list, g_list_copy (deprange->cell_list));
1150 1151
}

1152 1153 1154 1155 1156 1157 1158 1159 1160 1161
/**
 * sheet_region_get_deps :
 * Get a list of the elements that depend on the specified range.
 *
 * @sheet : The sheet.
 * @start_col : The target range.
 * @start_row :
 * @end_col :
 * @end_row :
 */
1162
GList *
1163 1164
sheet_region_get_deps (Sheet *sheet,
		       int start_col, int start_row, int end_col,  int end_row)
1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179
{
	int                      ix, iy;
	get_range_dep_closure_t  closure;

	g_return_val_if_fail (sheet != NULL, NULL);

	closure.r.start.col = start_col;
	closure.r.start.row = start_row;
	closure.r.end.col   = end_col;
	closure.r.end.row   = end_row;
	closure.list        = NULL;

	g_hash_table_foreach (sheet->deps->range_hash,
			      &search_range_deps, &closure);

1180 1181 1182 1183 1184 1185
	if (end_col > sheet->cols.max_used)
		end_col = sheet->cols.max_used;

	if (end_row > sheet->rows.max_used)
		end_row = sheet->rows.max_used;

1186 1187 1188 1189
	for (ix = start_col; ix <= end_col; ix++) {
		for (iy = start_row; iy <= end_row; iy++) {
			GList *l = get_single_dependencies (sheet, ix, iy);

1190
			closure.list = g_list_concat (closure.list, l);
1191 1192 1193 1194 1195 1196
		}
	}

	return closure.list;
}

1197 1198 1199
static void
cb_sheet_get_all_depends (gpointer key, gpointer value, gpointer closure)
{
1200 1201
	DependencyRange *deprange = key;
	GList          **deps     = closure;
1202

1203
	*deps = g_list_concat (*deps, g_list_copy (deprange->cell_list));
1204 1205 1206
}

static void
1207
cb_single_get_all_depends (gpointer key, gpointer value, gpointer closure)
1208
{
1209 1210 1211 1212
	DependencySingle *single = value;
	GList           **deps = closure;

	*deps = g_list_concat (*deps, g_list_copy (single->cell_list));
1213 1214 1215 1216
}

/**
 * sheet_recalc_dependencies :
1217 1218
 * Queue a recalc of anything that depends on the cells in this sheet.
 * Do not actually recalc, just queue them up.
1219 1220 1221
 *
 * @sheet : The sheet.
 */
1222 1223 1224
void
sheet_recalc_dependencies (Sheet *sheet)
{
1225
	GList *deps = NULL;
1226 1227 1228

	g_return_if_fail (sheet != NULL);
	g_return_if_fail (IS_SHEET (sheet));
1229
	g_return_if_fail (sheet->deps != NULL);
1230

1231
	/* Find anything that depends on a range in this sheet */
1232 1233 1234
	g_hash_table_foreach (sheet->deps->range_hash,
			      &cb_sheet_get_all_depends, &deps);

1235 1236 1237
	/* Find anything that depends on a single reference within this sheet */
	g_hash_table_foreach (sheet->deps->single_hash,
			      &cb_single_get_all_depends, &deps);
1238

1239
	if (deps)
Jody Goldberg's avatar
Jody Goldberg committed
1240
		eval_queue_list (deps, TRUE);
1241
}
Michael Meeks's avatar
Michael Meeks committed
1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263

/*
 * Ok; so we will have some new semantics;
 */

/*
CELL_QUEUED_FOR_RECALC will signify that the cell is in fact in the
recalc list. This means this cell will have to be re-calculated, it
also means that _All_ its dependencies are also in the re-calc list.

Hence; whenever a cell is added to the recalc list; its dependency
tree, must be progressively added to the list. Clearly any entries
marked 'CELL_QUEUED_FOR_RECALC' are already in there ( as are their
children ) so we can quickly and efficiently prune the tree.

The advantage of this is that we can dispense with the generation
scheme, with its costly linear reset ( even though amortized over
255 calculations it is an expense. ) We also have the _Luxury_ of
leaving things uncalculated with no loss of efficiency in the
queue. This will allow us to do far less re-calculating.

*/