slice.c

一个很不错的程序切片工具,希望大家来讨论以下,对测试人员很有帮助

		add_stmt_to_slice (pid,f,procs[pid].exit,slice_sets[f],(stmt_ptr)NULL);
		r = procs[pid].return_stmts;
		while (r){
			add_stmt_to_slice (pid,f,r->id,slice_sets[f],(stmt_ptr)NULL);
			r = r -> next;
		}
	}
	bit_on (active,pid);
	/* for (i = procs[pid].entry; i <= procs[pid].exit; i++) */
	union_bit_set (files[f].stmts[procs[pid].exit].active_global,
		files[fs].stmts[call->stmt].active_global);
	others = files[fs].stmts[call->stmt].active_other;
	while (others){
		if (others->pid == pid)
			bit_on(files[f].stmts[procs[pid].exit].active_local,
				others->id);
		else add_to_id_set (
			&files[f].stmts[procs[pid].exit].active_other,
			others->pid,others->id);
		others = others->next;
	}
	at = -1;
	while ((at = get_next_member(
			files[fs].stmts[call->stmt].active_local,at)) >= 0){
		change = add_to_id_set (
			&files[f].stmts[procs[pid].exit].active_other,
			proc,at);
	}
	slice_proc(final,slice_sets,pid,active);
	export_called_active (call,pid,proc,call->stmt);
}

int globals_defed(call,succ,pid)
	call_ptr	call;
	int			pid,succ;
{
	int		stmt,f;
	int		at;
	id_set_ptr others;

	if (!procs[call->pid].global_defs && !procs[call->pid].other_defs)
		return 0;
	stmt = call->stmt;
	f = procs[pid].file_id;
	/*
	at = -1;
	while ((at = get_next_member(
			files[f].stmts[succ].active_global,at)) >= 0){
		printf ("active %s\n",var_name (0,at));
	}
	*/
	at = -1;
	while ((at = get_next_member(procs[call->pid].global_defs,at)) >=
			0){
		if(v_opt)printf ("%s\n",var_name (0,at));
		if (is_bit_on (files[f].stmts[succ].active_global,at))
			return 1;
	}
	others = procs[call->pid].other_defs;
	while (others){
		if (others->pid == pid){
			if (is_bit_on (
				files[f].stmts[succ].active_local,others->id)){
					if(v_opt)
						printf ("var %s defed in call to %s from %s\n",
							var_name(pid,others->id),
							procs[call->pid].proc_name,
							procs[pid].proc_name);
					return 1;
			}
		}
		else if (is_in_id_set (files[f].stmts[succ].active_other,
			others->pid,others->id)) return 1;
		others = others -> next;
	}
	return 0;
}

int active_actuals(call,succ,pid)
	call_ptr	call;
	int			pid,succ;
{
	int		stmt,f;
	actual_ptr	act;
	var_ptr		refs;
	int			var_id,proc_id;
	bit_set		active;

	if(v_opt)printf ("any actuals ptr to active?\n");
	stmt = call->stmt;
	f = procs[pid].file_id;
	act = call->actuals;
	while (act){
		refs = act->actuals;
		while(refs){
			switch (refs->code){
			case LIF_AREF:
				proc_id = addrs[refs->id].pid;
				var_id  = addrs[refs->id].id;
				if(v_opt)printf ("actual aref to %s at %d from %d  ",
					var_name(proc_id,var_id),stmt,succ);
				active = proc_id?files[f].stmts[succ].active_local:
					files[f].stmts[succ].active_global;
				if (is_bit_on(active,var_id)) if(v_opt)printf ("active\n");
				else if(v_opt)printf ("not\n");
				if (is_bit_on(active,var_id)) return 1;
				break;
			case LIF_REF:
				break;
			case LIF_GREF:
				break;
			case LIF_CREF:
				break;
			default: ;
			}
			refs = refs -> next;
		}
		act = act -> next;
	}
	return 0;
}
int lib_def_active(calling_proc,f,stmt,succ,call)
	call_ptr	call;
	int			calling_proc,f,stmt,succ;
{
	int		called_proc;
	actual_ptr	act;
	int status = 0;
	var_ptr		var;
	int			id,pid;
	bit_set		active;

	called_proc = call ->pid;
	act = call->actuals;
	while (act){
		var = act->actuals;
		while (var){
			switch (var->code){
			case LIF_AREF:
				id = addrs[var->id].id;
				pid = addrs[var->id].pid;
				if (pid == calling_proc)
					active = files[f].stmts[succ].active_local;
				else if (!pid)
					active = files[f].stmts[succ].active_global;
				else active = NULL;
				if (active && is_bit_on (active,id)){
					add_to_active (f,stmt,pid,id,calling_proc);
					status = 1;
				}
				break;
			case LIF_CREF:
				break;
			case LIF_REF:
				break;
			case LIF_GREF:
				break;
			default: ;
			}
			var = var -> next;
		}
		act = act -> next;
	}
	return status;
}

add_req_set(f,pid,s,slice)
	int	f,s,pid;
	bit_set	slice;
{
	set_ptr	r;

	r = files[f].stmts[s].requires;
	while (r){
		add_stmt_to_slice (pid,f,r->id,slice,(stmt_ptr)NULL);
		r = r -> next;
	}
}
	

int check_calls (fs,slices,proc,stmt,succ,active)
	int		proc,stmt;
	set_ptr	succ;
	bit_set	fs[],slices[];
	bit_set	active;
{
	call_ptr	calls;
	int			status;
	int			f;

	status = 0;
	f = procs[proc].file_id;
	calls = files[f].stmts[stmt].calls;
	if (!calls) return status;
	if(v_opt)printf ("\ncheck calls at %d (succ %d)\n",stmt,succ->id);
	while (calls){
		if (procs[calls->pid].entry == -1)
			if(v_opt)printf ("Library ");
		if(v_opt)printf ("call %s at %d\n",procs[calls->pid].proc_name,
			calls->stmt);
		if (procs[calls->pid].entry == -1){
			if (lib_def_active(proc,f,stmt,succ->id,calls)){
				bit_on (slices[f],stmt);
				add_req_set(f,proc,stmt,slices[f]);
			}
			if (is_bit_on (slices[f],stmt))
				add_actuals (proc,calls);
		}
		else {
			if (active_actuals(calls,succ->id,proc)){
				bit_on (slices[f],stmt);
			}
			else if (globals_defed(calls,succ->id,proc)){
				bit_on (slices[f],stmt);
			}
			if (is_bit_on (slices[f],stmt)){
				add_req_set(f,proc,stmt,slices[f]);
				slice_across_call (fs,slices,calls,proc,active);
				/*
				add_actuals (proc,calls);
				*/
			}
		}
		calls = calls->next_this_stmt;
	}
	return status;
}


int slice_pass (fs,slices,proc,up,active)
	bit_set	slices[],fs[];
	int		proc,up;
	bit_set	active;
{
	bit_set	slice;
	int		from,to,delta,file,stmt;
	int		change = 0,inc;
	set_ptr	succ;

	file = procs[proc].file_id;
	slice = slices[file];
	if (up){
		from = procs[proc].entry;
		to = procs[proc].exit + 1;
		delta = 1;
	}
	else {
		to = procs[proc].entry - 1;
		from = procs[proc].exit;
		delta = -1;
	}
	stmt = from;
	while ((stmt >= procs[proc].entry) &&
			(stmt <= procs[proc].exit)){
		if (slice_hook)	(*slice_hook)(proc,stmt);
		succ = files[file].stmts[stmt].succ;
		while (succ){
			if (active_defed (file,stmt,succ->id,proc)){
				inc = add_stmt_to_slice(proc,file,stmt,slice,
					&files[file].stmts[succ->id]);
				change += inc;
				change += check_calls (fs,slices,proc,stmt,succ,active);
			}
			else {
				inc = pass_criteria (file,stmt,succ->id);
				change += inc;
				change += check_calls (fs,slices,proc,stmt,succ,active);
			}
			succ = succ -> next;
		}
		stmt = files[file].stmts[stmt].visit_next;
	}
	if(v_opt)print_active (proc,slice);
	if (slice_pass_hook)	(*slice_pass_hook)(proc,change);
	return change;
}

slice_tree (slices,proc,active)
	bit_set		active,slices[];
	int			proc;
{
	int			p,caller_pid,caller_file;
	int			change,n = 0;
	call_ptr	caller;

	clear_bit_set (active);
	bit_on (active,proc);
	caller_pid = proc;
	caller_file = procs[caller_pid].file_id;
	add_stmt_to_slice (caller_pid,caller_file,
		procs[caller_pid].entry,
		slices[caller_file],(stmt_ptr)NULL);
	add_stmt_to_slice (caller_pid,caller_file,
		procs[caller_pid].exit,
		slices[caller_file],(stmt_ptr)NULL);
	change = 1;
	while (change){
		change = 0;
		p = -1;
		while ((p = get_next_member(active,p)) >= 0){
			caller = procs[p].called_by;
			while (caller){
				caller_pid = caller->pid;
				caller_file = procs[caller_pid].file_id;
				if (!is_bit_on (slices[caller_file],caller->stmt)) {
					change = 1;
					add_stmt_to_slice (caller_pid,caller_file,
						caller->stmt, slices[caller_file],(stmt_ptr)NULL);
					bit_on (active,caller->pid);
					add_stmt_to_slice (caller_pid,caller_file,
						procs[caller_pid].entry,
						slices[caller_file],(stmt_ptr)NULL);
					add_stmt_to_slice (caller_pid,caller_file,
						procs[caller_pid].exit,
						slices[caller_file],(stmt_ptr)NULL);
					/* add caller to slice; */
				}
				caller = caller -> next;
			}
		}
	}
}

add_call_to_slice (slice_sets,proc,call)
	bit_set	slice_sets[];
	int		proc;
	call_ptr	call;
{
	set_ptr		return_at;

	if (procs[call->pid].entry == -1){
	/* undefined function: should look for library info */
		/* add actuals to active set */
	}
	else { /* defined proc */
		/*
		if (procs[proc].returns_xpr)
		*/
			if(v_opt)printf ("returns %d ",procs[call->pid].returns_xpr);
		return_at = procs[call->pid].return_stmts;
		if(return_at)if(v_opt)printf ("(");
		while (return_at){
			if(v_opt)printf ("%d",return_at->id);
			return_at = return_at -> next;
			if(return_at)if(v_opt)printf (",");
			else if(v_opt)printf (") ");
		}
	}
}

slice_up (final_slice_sets,slice_sets,proc,active,dont_slice)
	int		proc;
	bit_set	final_slice_sets[],slice_sets[];
	bit_set	active,dont_slice;
{
	call_ptr	calls;

	/* printf ("\nSLICE UP %s\n",procs[proc].proc_name);*/
	clear_bit_set (dont_descend);
	slice_proc(final_slice_sets,slice_sets,proc,active);
	if (procs[proc].entry == -1) return;
	if (is_bit_on(dont_slice,proc))return;
	calls = procs[proc].called_by;
	bit_on (dont_slice,proc);
	while (calls){
		export_called_active (calls,
			proc,calls->pid,calls->stmt);
		slice_up (final_slice_sets,slice_sets,
			calls->pid,active,dont_slice);
		calls = calls -> next;
	}
}

int call_pass (slice_sets,proc) /* d e a d    c o d e */
	bit_set	slice_sets[];
	int		proc;
{
	int		status = 0;
	call_ptr	calls;
	int		file;

	calls = procs[proc].calls;
	file = procs[proc].file_id;
	while (calls){
		if (is_bit_on (slice_sets[file],calls->stmt)){
			add_call_to_slice (slice_sets,proc,calls);
			if(v_opt)printf ("in slice ");
		}
		if (procs[calls->pid].entry == -1)
			if(v_opt)printf ("Library ");
		if(v_opt)printf ("call %s at %d\n",procs[calls->pid].proc_name,
			calls->stmt);
		calls = calls->next;
	}
	return status;
}

slice_proc (final_slice_sets,slice_sets,proc,active)
	int		proc;
	bit_set	final_slice_sets[],slice_sets[];
	bit_set	active;
{
	int		i,status;
	int		pid = proc;

	if(v_opt)printf ("enter slice proc on %s\n",procs[proc].proc_name); 
	if(is_bit_on (dont_descend,proc)) return; /* don't recurse */
	bit_on (dont_descend,proc);
	if(v_opt)printf ("start slice proc on %s\n",procs[proc].proc_name);
	status = 1;
    while (status){
		if (abandon_slice) return;
/*		printf ("pass start %s\n",procs[proc].proc_name); */
        status = slice_pass (final_slice_sets,slice_sets,proc,0,active);
/*		printf ("pass end   %s %d\n",procs[proc].proc_name,status); */
    }
	i = procs[proc].file_id;
	union_bit_set (final_slice_sets[i],slice_sets[i]);
	/*CheckW(QQQ);*/
	if(v_opt)printf ("end slice proc on %s\n",procs[proc].proc_name);
	bit_off (dont_descend,proc);
}

/*
*********************************************************************
*                                                                   *
*  main control for computing a slice                               *
*  criterion --                                                     *
*     file      file id of file containing stmt                     *
*     proc      proc containing criterion statement                 *
*     stmt      criterion statement (node)                          *
*     var_proc  proc id of var (if local) or 0 (if var global)      *
*     var       criterion var                                       *
*                                                                   *
*  results --                                                       *
*     slice_sets bit sets (one per file) marking stmts in slice     *
*     active     bit set marking procs in the slice                 *
*                                                                   *
*********************************************************************
*/
slice (file,proc,stmt,var_proc,var,final_slice_sets,active)
	int file,proc,stmt,var_proc,var;
	bit_set	final_slice_sets[],active;
{
	int		i,status,call_status;
	static	bit_set	*slice_sets,dont_slice = NULL;
	static	int	need = 1;

	abandon_slice = 0;
	if (!dont_slice){
		dont_slice = create_bit_set (n_procs+1);
		dont_descend = create_bit_set (n_procs+1);
	}
	clear_bit_set (dont_slice);
	if (need){
		need = 0;
		slice_sets = (bit_set *) malloc (n_files*sizeof(bit_set));
		if (!slice_sets){
			fprintf (stderr,"Out of memory in slice\n");
			exit(1);
		}
		for (i = 0; i < n_files; i++)
			slice_sets[i] = create_bit_set (1+files[i].n_stmts);
		/*
		printf ("creating slice sets for %d files\n",n_files);
		for (i = 0; i < n_files; i++){
			printf ("%d  %d  %d\n",i,final_slice_sets[i]->max,
				slice_sets[i]->max);
		}
		*/
	}
	clear_active();
    for (i = 0; i < n_files; i++)
        clear_bit_set (final_slice_sets[i]);
    for (i = 0; i < n_files; i++)
        clear_bit_set (slice_sets[i]);
    clear_bit_set (active);
    slice_tree (final_slice_sets,proc,active);
    set_criteria (file,proc,stmt,var_proc,var);
	/*
	slice_proc(final_slice_sets,slice_sets,proc,active);
	*/
	slice_up (final_slice_sets,slice_sets,proc,active,dont_slice);

}

# define LINE_LENGTH 67
print_slices (print_nodes,slices,active)
	bit_set	slices[],active;
	int		print_nodes;
{
	int			file,proc;
	int			stmt,count;
	int			line;

	proc = -1;
	while ((proc = get_next_member(active,proc)) >= 0){
		if (procs[proc].entry > 0){
			file = procs[proc].file_id;
			printf ("\n%s'%s\n",files[file].name,procs[proc].proc_name);
			count = 0;
			stmt = -1;
			while ((stmt = get_next_member(slices[file],stmt)) >= 0){
				if (print_nodes)count += printf ("%4d ",stmt);
				else {
					line = files[file].stmts[stmt].froml;
					count += printf ("%4d ",line);
				}
				if (count > LINE_LENGTH) {
					printf ("\n");
					count = 0;
				}
			}
			if (count) printf ("\n");
		}
	}
}
print_slices1 (print_nodes,slices,active)
	bit_set	slices[],active;
	int		print_nodes;
{
	int			file,proc;
	int			stmt,count;
	int			line,from,to;
	int			max = 0,f;
	static 		bit_set		map = NULL;

	if (!print_nodes && !map){
		for (f = 0; f < n_files; f++)
			if (max < files[f].n_lines) max = files[f].n_lines;
		map = create_bit_set (max+1);
	}
	for (file = 0; file < n_files; file++){
		count = printf ("    %sc: ",files[file].name);
		stmt = -1;
		if(!print_nodes)clear_bit_set (map);
		while ((stmt = get_next_member(slices[file],stmt)) >= 0){
			if (print_nodes)count += printf ("%4d ",stmt);
			else {
				from = files[file].stmts[stmt].froml;
				to = files[file].stmts[stmt].tol;
				bit_on (map,from);
				for (line = from+1; line <= to; line++)
					bit_on (map,line);
			}
			if (count > LINE_LENGTH) {
				printf ("\n");
				count = 0;
			}
		}
		if (!print_nodes){
			line = -1;
			while ((line = get_next_member(map,line)) >= 0){
				count += printf ("%4d ",line);
				if (count > LINE_LENGTH) {
					printf ("\n");
					count = 0;
				}
			}
		}
		if (count) printf ("\n");
	}
}