dependent.c 11 KB
Newer Older
Arturo Espinosa's avatar
Arturo Espinosa committed
1 2 3 4 5 6 7 8 9 10 11 12
/*
 * eval.c:  Cell recomputation routines.
 *
 * Author:
 *  Miguel de Icaza (miguel@gnu.org)
 */

#include <config.h>
#include <gnome.h>
#include "gnumeric.h"
#include "gnumeric-sheet.h"
#include "utils.h"
13 14
#include "eval.h"

Morten Welinder's avatar
Morten Welinder committed
15 16
#undef DEBUG_EVALUATION

Arturo Espinosa's avatar
Arturo Espinosa committed
17
static GHashTable *dependency_hash;
Arturo Espinosa's avatar
Arturo Espinosa committed
18 19

void
Arturo Espinosa's avatar
Arturo Espinosa committed
20
cell_eval (Cell *cell)
Arturo Espinosa's avatar
Arturo Espinosa committed
21 22
{
	Value *v;
23
	FunctionEvalInfo s;
Arturo Espinosa's avatar
Arturo Espinosa committed
24

25
	g_return_if_fail (cell != NULL);
Arturo Espinosa's avatar
Arturo Espinosa committed
26

Morten Welinder's avatar
Morten Welinder committed
27 28
#ifdef DEBUG_EVALUATION
	{
29 30
		EvalPosition fp;
		
Morten Welinder's avatar
Morten Welinder committed
31
		char *exprtxt = expr_decode_tree
32
			(cell->parsed_node, eval_pos_cell (&fp, cell));
Morten Welinder's avatar
Morten Welinder committed
33 34 35 36 37 38 39
		printf ("Evaluating %s: %s ->\n",
			cell_name (cell->col->pos, cell->row->pos),
			exprtxt);
		g_free (exprtxt);
	}
#endif

Morten Welinder's avatar
Morten Welinder committed
40
	v = eval_expr (func_eval_info_cell (&s, cell), cell->parsed_node);
Arturo Espinosa's avatar
Arturo Espinosa committed
41

Morten Welinder's avatar
Morten Welinder committed
42 43 44 45 46 47 48 49 50 51 52 53
#ifdef DEBUG_EVALUATION
	{
		char *valtxt = v
			? value_get_as_string (v)
			: g_strdup ("NULL");
		printf ("Evaluating %s: -> %s\n",
			cell_name (cell->col->pos, cell->row->pos),
			valtxt);
		g_free (valtxt);
	}
#endif

54
	if (cell->value){
Arturo Espinosa's avatar
Arturo Espinosa committed
55
		value_release (cell->value);
56 57
		cell->value = NULL;
	}
Morten Welinder's avatar
Morten Welinder committed
58

Arturo Espinosa's avatar
Arturo Espinosa committed
59
	if (v == NULL){
60
		cell_set_rendered_text (cell, error_message_txt (s.error));
Arturo Espinosa's avatar
Arturo Espinosa committed
61
		cell->value = NULL;
62
		cell->flags |= CELL_ERROR;
Arturo Espinosa's avatar
Arturo Espinosa committed
63 64
	} else {
		cell->value = v;
Miguel de Icaza's avatar
Miguel de Icaza committed
65
		cell_render_value (cell);
66
		cell->flags &= ~CELL_ERROR;
Arturo Espinosa's avatar
Arturo Espinosa committed
67 68
	}

Morten Welinder's avatar
Morten Welinder committed
69 70
	error_message_free (s.error);

71
	cell_calc_dimensions (cell);
Morten Welinder's avatar
Morten Welinder committed
72

Arturo Espinosa's avatar
Arturo Espinosa committed
73
	sheet_redraw_cell_region (cell->sheet,
Arturo Espinosa's avatar
Arturo Espinosa committed
74 75 76 77
				  cell->col->pos, cell->row->pos,
				  cell->col->pos, cell->row->pos);
}

78 79 80 81 82 83
/*
 * Comparission function for the dependency hash table
 */
static gint
dependency_equal (gconstpointer v, gconstpointer v2)
{
Morten Welinder's avatar
Morten Welinder committed
84 85
	const DependencyRange *r1 = (const DependencyRange *) v;
	const DependencyRange *r2 = (const DependencyRange *) v2;
86 87 88

	if (r1->sheet != r2->sheet)
		return 0;
89
	if (r1->range.start_col != r2->range.start_col)
90
		return 0;
91
	if (r1->range.start_row != r2->range.start_row)
92
		return 0;
93
	if (r1->range.end_col != r2->range.end_col)
94
		return 0;
95
	if (r1->range.end_row != r2->range.end_row)
96 97 98 99 100 101 102 103 104
		return 0;

	return 1;
}

/*
 * Hash function for DependencyRange structures
 */
static guint
Arturo Espinosa's avatar
Arturo Espinosa committed
105
dependency_hash_func (gconstpointer v)
106
{
Arturo Espinosa's avatar
Arturo Espinosa committed
107
	const DependencyRange *r = v;
108

109 110
	return ((((r->range.start_row << 8) + r->range.end_row) << 8) +
		(r->range.start_col << 8) + (r->range.end_col));
111 112 113 114 115 116 117 118
}

/*
 * Initializes the hash table for the dependency ranges
 */
static void
dependency_hash_init (void)
{
Arturo Espinosa's avatar
Arturo Espinosa committed
119
	dependency_hash = g_hash_table_new (dependency_hash_func, dependency_equal);
120 121 122 123 124 125 126 127 128
}

/*
 * We add the dependency of Cell a in the ranges
 * enclose by CellRef a and CellRef b
 *
 * We compute the location from cell->row->pos and cell->col->pos
 */
static void
129
add_cell_range_deps (Cell *cell, const CellRef *a, const CellRef *b)
130 131 132 133 134 135
{
	DependencyRange range, *result;
	int col = cell->col->pos;
	int row = cell->row->pos;

	/* Convert to absolute cordinates */
136 137
	cell_get_abs_col_row (a, col, row, &range.range.start_col, &range.range.start_row);
	cell_get_abs_col_row (b, col, row, &range.range.end_col,   &range.range.end_row);
Arturo Espinosa's avatar
Arturo Espinosa committed
138 139 140

	range.ref_count = 0;
	range.sheet = cell->sheet;
141 142 143 144

	/* Look it up */
	result = g_hash_table_lookup (dependency_hash, &range);
	if (result){
Arturo Espinosa's avatar
Arturo Espinosa committed
145
		GList *cl;
Morten Welinder's avatar
Morten Welinder committed
146

147 148 149
		result->ref_count++;

		/* Is the cell already listed? */
Arturo Espinosa's avatar
Arturo Espinosa committed
150 151
		cl = g_list_find (result->cell_list, cell);
		if (cl)
152 153 154 155 156 157 158
			return;

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

Morten Welinder's avatar
Morten Welinder committed
159
	/* Create a new DependencyRange structure */
160 161
	result = g_new (DependencyRange, 1);
	*result = range;
Arturo Espinosa's avatar
Arturo Espinosa committed
162 163
	result->ref_count = 1;
	result->cell_list = g_list_prepend (NULL, cell);
164

165 166 167 168 169 170 171
	g_hash_table_insert (dependency_hash, result, result);
}

/*
 * Adds the dependencies for a Value
 */
static void
172
add_value_deps (Cell *cell, const Value *value)
173
{
Arturo Espinosa's avatar
Arturo Espinosa committed
174
	switch (value->type){
175 176 177 178 179
	case VALUE_STRING:
	case VALUE_INTEGER:
	case VALUE_FLOAT:
		/* Constants are no dependencies */
		break;
Morten Welinder's avatar
Morten Welinder committed
180

181 182
		/* Check every element of the array */
	case VALUE_ARRAY:
183
	{
184
		int x, y;
Morten Welinder's avatar
Morten Welinder committed
185

186 187
		for (x = 0; x < value->v.array.x; x++)
			for (y = 0; y < value->v.array.y; y++)
188
				add_value_deps (cell,
189
						value->v.array.vals [x][y]);
190
		break;
191
	}
192 193
	case VALUE_CELLRANGE:
		add_cell_range_deps (
Arturo Espinosa's avatar
Arturo Espinosa committed
194 195 196
			cell,
			&value->v.cell_range.cell_a,
			&value->v.cell_range.cell_b);
197 198 199 200 201 202 203 204 205
		break;
	}
}

/*
 * This routine walks the expression tree looking for cell references
 * and cell range references.
 */
static void
Arturo Espinosa's avatar
Arturo Espinosa committed
206
add_tree_deps (Cell *cell, ExprTree *tree)
207
{
Arturo Espinosa's avatar
Arturo Espinosa committed
208
	GList *l;
Morten Welinder's avatar
Morten Welinder committed
209

210
	switch (tree->oper){
Morten Welinder's avatar
Morten Welinder committed
211
	case OPER_ANY_BINARY:
Arturo Espinosa's avatar
Arturo Espinosa committed
212 213
		add_tree_deps (cell, tree->u.binary.value_a);
		add_tree_deps (cell, tree->u.binary.value_b);
214 215
		return;

Morten Welinder's avatar
Morten Welinder committed
216 217 218
	case OPER_ANY_UNARY:
		add_tree_deps (cell, tree->u.value);
		return;
Morten Welinder's avatar
Morten Welinder committed
219 220

	case OPER_VAR:
221 222 223 224 225 226
		add_cell_range_deps (
			cell,
			&tree->u.ref,
			&tree->u.ref);
		return;

227
	case OPER_CONSTANT:
Arturo Espinosa's avatar
Arturo Espinosa committed
228
		add_value_deps (cell, tree->u.constant);
229 230
		return;

Morten Welinder's avatar
Morten Welinder committed
231
	case OPER_FUNCALL:
232
		for (l = tree->u.function.arg_list; l; l = l->next)
Arturo Espinosa's avatar
Arturo Espinosa committed
233
			add_tree_deps (cell, l->data);
234 235 236 237 238 239 240 241 242 243 244
		return;

	} /* switch */
}

/*
 * This registers the dependencies for this cell
 * by scanning all of the references made in the
 * parsed expression.
 */
void
Arturo Espinosa's avatar
Arturo Espinosa committed
245
cell_add_dependencies (Cell *cell)
246 247 248
{
	g_return_if_fail (cell != NULL);
	g_return_if_fail (cell->parsed_node != NULL);
Morten Welinder's avatar
Morten Welinder committed
249

250 251 252
	if (!dependency_hash)
		dependency_hash_init ();

Arturo Espinosa's avatar
Arturo Espinosa committed
253
	add_tree_deps (cell, cell->parsed_node);
254 255 256 257 258 259 260 261 262 263 264 265 266 267
}

/*
 * List used by cell_drop_dependencies and dependency_remove_cell
 * to accumulate all of the "dead" DependencyRange structures.
 *
 * Once the table_foreach process has finished, these are released
 */
static GList *remove_list;

static void
dependency_remove_cell (gpointer key, gpointer value, gpointer the_cell)
{
	DependencyRange *range = value;
268
	GList *list;
269 270 271 272

	list = g_list_find (range->cell_list, the_cell);
	if (!list)
		return;
Arturo Espinosa's avatar
Arturo Espinosa committed
273

274
	range->cell_list = g_list_remove_link (range->cell_list, list);
Morten Welinder's avatar
Morten Welinder committed
275 276
	g_list_free_1 (list);

277 278 279 280 281 282 283 284 285 286 287 288 289
	range->ref_count--;

	if (range->ref_count == 0)
		remove_list = g_list_prepend (remove_list, range);
}

/*
 * Remove the Cell from the DependecyRange hash tables
 */
void
cell_drop_dependencies (Cell *cell)
{
	g_return_if_fail (cell != NULL);
290
	g_return_if_fail (cell->parsed_node != NULL);
Morten Welinder's avatar
Morten Welinder committed
291

292 293
	if (!dependency_hash)
		return;
Morten Welinder's avatar
Morten Welinder committed
294

295 296
	g_hash_table_foreach (dependency_hash, dependency_remove_cell, cell);

Arturo Espinosa's avatar
Arturo Espinosa committed
297
	/* Drop any unused DependencyRanges (because their ref_count reached zero) */
298 299
	if (remove_list){
		GList *l = remove_list;
Morten Welinder's avatar
Morten Welinder committed
300

301
		for (; l; l = l->next){
Arturo Espinosa's avatar
Arturo Espinosa committed
302
			g_hash_table_remove (dependency_hash, l->data);
303
			g_free (l->data);
Arturo Espinosa's avatar
Arturo Espinosa committed
304
		}
Morten Welinder's avatar
Morten Welinder committed
305

306 307 308 309 310 311
		g_list_free (remove_list);
		remove_list = NULL;
	}
}

typedef struct {
Arturo Espinosa's avatar
Arturo Espinosa committed
312 313
	int   start_col, start_row;
	int   end_col, end_row;
314 315 316 317
	Sheet *sheet;
	GList *list;
} get_dep_closure_t;

Arturo Espinosa's avatar
Arturo Espinosa committed
318 319 320
static gboolean
intersects (Sheet *sheet, int col, int row, DependencyRange *range)
{
Michael Meeks's avatar
Michael Meeks committed
321 322
	if ((sheet == range->sheet) &&
	    range_contains (&range->range, col, row))
Arturo Espinosa's avatar
Arturo Espinosa committed
323 324 325 326 327
		return TRUE;

	return FALSE;
}

328 329 330
static void
search_cell_deps (gpointer key, gpointer value, gpointer closure)
{
Arturo Espinosa's avatar
Arturo Espinosa committed
331
	DependencyRange *range = key;
332
	get_dep_closure_t *c = closure;
Arturo Espinosa's avatar
Arturo Espinosa committed
333
	Sheet *sheet = c->sheet;
Arturo Espinosa's avatar
Arturo Espinosa committed
334
	GList *l;
Michael Meeks's avatar
Michael Meeks committed
335 336

	/* No intersection is the common case */
337

Arturo Espinosa's avatar
Arturo Espinosa committed
338 339 340 341 342
	if (!(intersects (sheet, c->start_col, c->start_row, range) ||
	      intersects (sheet, c->end_col,   c->end_row,   range) ||
	      intersects (sheet, c->start_col, c->end_row,   range) ||
	      intersects (sheet, c->end_col,   c->start_row, range)))
		return;
Michael Meeks's avatar
Michael Meeks committed
343

Arturo Espinosa's avatar
Arturo Espinosa committed
344 345 346
	for (l = range->cell_list; l; l = l->next){
		Cell *cell = l->data;

347
		c->list = g_list_prepend (c->list, cell);
Arturo Espinosa's avatar
Arturo Espinosa committed
348
	}
349 350
}

Arturo Espinosa's avatar
Arturo Espinosa committed
351 352 353 354 355 356 357
GList *
region_get_dependencies (Sheet *sheet, int start_col, int start_row, int end_col, int end_row)
{
	get_dep_closure_t closure;

	if (!dependency_hash)
		dependency_hash_init ();
Morten Welinder's avatar
Morten Welinder committed
358

Arturo Espinosa's avatar
Arturo Espinosa committed
359 360 361 362
	closure.start_col = start_col;
	closure.start_row = start_row;
	closure.end_col = end_col;
	closure.end_row = end_row;
Arturo Espinosa's avatar
Arturo Espinosa committed
363 364 365 366 367 368 369 370
	closure.sheet = sheet;
	closure.list = NULL;

	g_hash_table_foreach (dependency_hash, &search_cell_deps, &closure);

	return closure.list;
}

371 372 373 374 375
GList *
cell_get_dependencies (Sheet *sheet, int col, int row)
{
	get_dep_closure_t closure;

Arturo Espinosa's avatar
Arturo Espinosa committed
376 377
	if (!dependency_hash)
		dependency_hash_init ();
Morten Welinder's avatar
Morten Welinder committed
378

Arturo Espinosa's avatar
Arturo Espinosa committed
379 380 381 382
	closure.start_col = col;
	closure.start_row = row;
	closure.end_col = col;
	closure.end_row = row;
383 384
	closure.sheet = sheet;
	closure.list = NULL;
Arturo Espinosa's avatar
Arturo Espinosa committed
385 386

	g_hash_table_foreach (dependency_hash, &search_cell_deps, &closure);
387 388 389 390

	return closure.list;
}

391 392 393 394 395 396
/*
 * cell_queue_recalc:
 * @cell: the cell that contains the formula that must be recomputed
 *
 * Queues the cell @cell for recalculation.
 */
Arturo Espinosa's avatar
Arturo Espinosa committed
397 398 399 400 401 402
void
cell_queue_recalc (Cell *cell)
{
	Workbook *wb;

	g_return_if_fail (cell != NULL);
Morten Welinder's avatar
Morten Welinder committed
403

Morten Welinder's avatar
Morten Welinder committed
404 405 406
	if (cell->flags & CELL_QUEUED_FOR_RECALC)
		return;

Morten Welinder's avatar
Morten Welinder committed
407
	wb = cell->sheet->workbook;
Arturo Espinosa's avatar
Arturo Espinosa committed
408
	wb->eval_queue = g_list_prepend (wb->eval_queue, cell);
409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
	cell->flags |= CELL_QUEUED_FOR_RECALC;
}

/*
 * cell_unqueue_from_recalc:
 * @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
cell_unqueue_from_recalc (Cell *cell)
{
	Workbook *wb;
Morten Welinder's avatar
Morten Welinder committed
424

425 426 427 428 429
	g_return_if_fail (cell != NULL);

	if (!(cell->flags & CELL_QUEUED_FOR_RECALC))
		return;

Morten Welinder's avatar
Morten Welinder committed
430
	wb = cell->sheet->workbook;
431 432
	wb->eval_queue = g_list_remove (wb->eval_queue, cell);
	cell->flags &= ~CELL_QUEUED_FOR_RECALC;
Arturo Espinosa's avatar
Arturo Espinosa committed
433 434 435
}

void
Morten Welinder's avatar
Morten Welinder committed
436
cell_queue_recalc_list (GList *list, gboolean freelist)
Arturo Espinosa's avatar
Arturo Espinosa committed
437 438 439
{
	Workbook *wb;
	Cell *first_cell;
Morten Welinder's avatar
Morten Welinder committed
440 441
	GList *list0 = list;

Arturo Espinosa's avatar
Arturo Espinosa committed
442 443 444 445
	if (!list)
		return;

	first_cell = list->data;
Morten Welinder's avatar
Morten Welinder committed
446
	wb = first_cell->sheet->workbook;
Arturo Espinosa's avatar
Arturo Espinosa committed
447

448 449 450
	while (list) {
		Cell *cell = list->data;
		list = list->next;
Morten Welinder's avatar
Morten Welinder committed
451 452 453 454 455 456 457

		if (cell->flags & CELL_QUEUED_FOR_RECALC)
			continue;

		wb->eval_queue = g_list_prepend (wb->eval_queue, cell);

		cell->flags |= CELL_QUEUED_FOR_RECALC;
458
	}
Morten Welinder's avatar
Morten Welinder committed
459

Morten Welinder's avatar
Morten Welinder committed
460 461
	if (freelist)
		g_list_free (list0);
Arturo Espinosa's avatar
Arturo Espinosa committed
462 463 464 465
}

static Cell *
pick_next_cell_from_queue (Workbook *wb)
466
{
Arturo Espinosa's avatar
Arturo Espinosa committed
467 468 469 470
	Cell *cell;

	if (!wb->eval_queue)
		return NULL;
Morten Welinder's avatar
Morten Welinder committed
471

Arturo Espinosa's avatar
Arturo Espinosa committed
472 473
	cell = wb->eval_queue->data;
	wb->eval_queue = g_list_remove (wb->eval_queue, cell);
Michael Meeks's avatar
Michael Meeks committed
474 475
	if (!(cell->flags & CELL_QUEUED_FOR_RECALC))
		printf ("De-queued cell here\n");
476
	cell->flags &= ~CELL_QUEUED_FOR_RECALC;
Arturo Espinosa's avatar
Arturo Espinosa committed
477 478 479
	return cell;
}

480 481 482 483 484 485 486 487 488
/*
 * Increments the generation.  Every time the generation is
 * about to wrap around, we reset all of the cell counters to zero
 */
void
workbook_next_generation (Workbook *wb)
{
	if (wb->generation == 255){
		GList *cell_list = wb->formula_cell_list;
Morten Welinder's avatar
Morten Welinder committed
489

490 491 492 493 494 495 496 497 498 499
		for (; cell_list; cell_list = cell_list->next){
			Cell *cell = cell_list->data;

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

500 501 502 503
/*
 * Computes all of the cells pending computation and
 * any dependency.
 */
Arturo Espinosa's avatar
Arturo Espinosa committed
504 505 506
void
workbook_recalc (Workbook *wb)
{
507
	int generation;
Arturo Espinosa's avatar
Arturo Espinosa committed
508
	Cell *cell;
509 510 511

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

Arturo Espinosa's avatar
Arturo Espinosa committed
513
	while ((cell = pick_next_cell_from_queue (wb))){
Morten Welinder's avatar
Morten Welinder committed
514 515 516 517 518
		GList *deps, *l;

		if (cell->generation == generation)
			continue;

519
		cell->generation = generation;
Arturo Espinosa's avatar
Arturo Espinosa committed
520
		cell_eval (cell);
521
		deps = cell_get_dependencies (cell->sheet, cell->col->pos, cell->row->pos);
522

523
		for (l = deps; l; l = l->next){
524 525 526 527 528 529 530
			Cell *one_cell;

			one_cell = l->data;
			if (one_cell->generation != generation)
				cell_queue_recalc (one_cell);
		}
		g_list_free (deps);
Arturo Espinosa's avatar
Arturo Espinosa committed
531
	}
532
}
533 534 535 536 537 538 539

/*
 * Recomputes all of the formulas.
 */
void
workbook_recalc_all (Workbook *workbook)
{
Morten Welinder's avatar
Morten Welinder committed
540
	cell_queue_recalc_list (workbook->formula_cell_list, FALSE);
541 542
	workbook_recalc (workbook);
}