text: /*
     +----------------------------------------------------------------------+
     | Copyright (c) 1997-2019 Derick Rethans                               |
     +----------------------------------------------------------------------+
     | This source file is subject to the 2-Clause BSD license which is     |
     | available through the LICENSE file, or online at                     |
     | http://opensource.org/licenses/bsd-license.php                       |
     +----------------------------------------------------------------------+
     | Authors:  Derick Rethans <derick@derickrethans.nl>                   |
     +----------------------------------------------------------------------+
   */
  /* $Id: branch_info.c,v 1.1 2006-09-26 09:40:26 derick Exp $ */
  
  #include <stdlib.h>
  #include <math.h>
  #include "branchinfo.h"
  
  ZEND_EXTERN_MODULE_GLOBALS(vld)
  
  vld_branch_info *vld_branch_info_create(unsigned int size)
  {
  	vld_branch_info *tmp;
  
  	tmp = calloc(1, sizeof(vld_branch_info));
  	tmp->size = size;
  	tmp->branches = calloc(size, sizeof(vld_branch));
  	tmp->entry_points = vld_set_create(size);
  	tmp->starts       = vld_set_create(size);
  	tmp->ends         = vld_set_create(size);
  
  	tmp->paths_count = 0;
  	tmp->paths_size  = 0;
  	tmp->paths = NULL;
  
  	return tmp;
  }
  
  void vld_branch_info_free(vld_branch_info *branch_info)
  {
  	unsigned int i;
  
  	for (i = 0; i < branch_info->paths_count; i++) {
  		free(branch_info->paths[i]->elements);
  		free(branch_info->paths[i]);
  	}
  	free(branch_info->paths);
  	free(branch_info->branches);
  	vld_set_free(branch_info->entry_points);
  	vld_set_free(branch_info->starts);
  	vld_set_free(branch_info->ends);
  	free(branch_info);
  }
  
  void vld_branch_info_update(vld_branch_info *branch_info, unsigned int pos, unsigned int lineno, unsigned int outidx, unsigned int jump_pos)
  {
  	vld_set_add(branch_info->ends, pos);
  	if (branch_info->branches[pos].outs_count < VLD_BRANCH_MAX_OUTS) {
  		branch_info->branches[pos].outs[branch_info->branches[pos].outs_count] = jump_pos;
  		branch_info->branches[pos].outs_count++;
  	}
  
  	branch_info->branches[pos].start_lineno = lineno;
  }
  
  void vld_only_leave_first_catch(zend_op_array *opa, vld_branch_info *branch_info, int position)
  {
  	unsigned int exit_jmp;
  #if PHP_VERSION_ID >= 70300 && ZEND_USE_ABS_JMP_ADDR
  	zend_op *base_address = &(opa->opcodes[0]);
  #endif
  
  	if (opa->opcodes[position].opcode == ZEND_FETCH_CLASS) {
  		position++;
  	}
  
  	if (opa->opcodes[position].opcode != ZEND_CATCH) {
  		return;
  	}
  
  #if PHP_VERSION_ID >= 70300
  	if (!(opa->opcodes[position].extended_value & ZEND_LAST_CATCH)) {
  		exit_jmp = VLD_ZNODE_JMP_LINE(opa->opcodes[position].op2, position, base_address);
  #else
  	if (!opa->opcodes[position].result.num) {
  # if PHP_VERSION_ID >= 70100
  		exit_jmp = position + ((signed int) opa->opcodes[position].extended_value / sizeof(zend_op));
  # else
  		exit_jmp = opa->opcodes[position].extended_value;
  # endif
  #endif
  		if (opa->opcodes[exit_jmp].opcode == ZEND_FETCH_CLASS) {
  			exit_jmp++;
  		}
  		if (opa->opcodes[exit_jmp].opcode == ZEND_CATCH) {
  			vld_only_leave_first_catch(opa, branch_info, exit_jmp);
  		}
  	}
  
  	vld_set_remove(branch_info->entry_points, position);
  }
  
  void vld_branch_post_process(zend_op_array *opa, vld_branch_info *branch_info)
  {
  	unsigned int i;
  	int in_branch = 0, last_start = VLD_JMP_NOT_SET;
  #if PHP_VERSION_ID >= 70300 && ZEND_USE_ABS_JMP_ADDR
  	zend_op *base_address = &(opa->opcodes[0]);
  #endif
  
  	/* Figure out which CATCHes are chained, and hence which ones should be
  	 * considered entry points */
  	for (i = 0; i < branch_info->entry_points->size; i++) {
  		if (vld_set_in(branch_info->entry_points, i) && opa->opcodes[i].opcode == ZEND_CATCH) {
  #if PHP_VERSION_ID >= 70300
  # if ZEND_USE_ABS_JMP_ADDR
  			if (opa->opcodes[i].op2.jmp_addr != NULL) {
  # else
  			if (opa->opcodes[i].op2.jmp_offset != 0) {
  # endif
  				vld_only_leave_first_catch(opa, branch_info, VLD_ZNODE_JMP_LINE(opa->opcodes[i].op2, i, base_address));
  			}
  
  #elif PHP_VERSION_ID >= 70100
  			vld_only_leave_first_catch(opa, branch_info, i + ((signed int) opa->opcodes[i].extended_value / sizeof(zend_op)));
  #else
  			vld_only_leave_first_catch(opa, branch_info, opa->opcodes[i].extended_value);
  #endif
  		}
  	}
  
  	for (i = 0; i < branch_info->starts->size; i++) {
  		if (vld_set_in(branch_info->starts, i)) {
  			if (in_branch) {
  				branch_info->branches[last_start].outs_count = 1;
  				branch_info->branches[last_start].outs[0] = i;
  				branch_info->branches[last_start].end_op = i-1;
  				branch_info->branches[last_start].end_lineno = branch_info->branches[i].start_lineno;
  			}
  			last_start = i;
  			in_branch = 1;
  		}
  		if (vld_set_in(branch_info->ends, i)) {
  			size_t j;
  			for (j = 0; j < branch_info->branches[i].outs_count; j++) {
  				branch_info->branches[last_start].outs[j] = branch_info->branches[i].outs[j];
  			}
  			branch_info->branches[last_start].outs_count = branch_info->branches[i].outs_count;
  			branch_info->branches[last_start].end_op = i;
  			branch_info->branches[last_start].end_lineno = branch_info->branches[i].start_lineno;
  			in_branch = 0;
  		}
  	}
  }
  
  static void vld_path_add(vld_path *path, unsigned int nr)
  {
  	if (path->elements_count == path->elements_size) {
  		path->elements_size += 32;
  		path->elements = realloc(path->elements, sizeof(unsigned int) * path->elements_size);
  	}
  	path->elements[path->elements_count] = nr;
  	path->elements_count++;
  }
  
  static void vld_branch_info_add_path(vld_branch_info *branch_info, vld_path *path)
  {
  	if (branch_info->paths_count == branch_info->paths_size) {
  		branch_info->paths_size += 32;
  		branch_info->paths = realloc(branch_info->paths, sizeof(vld_path*) * branch_info->paths_size);
  	}
  	branch_info->paths[branch_info->paths_count] = path;
  	branch_info->paths_count++;
  }
  
  static vld_path *vld_path_new(vld_path *old_path)
  {
  	vld_path *tmp;
  	tmp = calloc(1, sizeof(vld_path));
  
  	if (old_path) {
  		unsigned i;
  
  		for (i = 0; i < old_path->elements_count; i++) {
  			vld_path_add(tmp, old_path->elements[i]);
  		}
  	}
  	return tmp;
  }
  
  static void vld_path_free(vld_path *path)
  {
  	if (path->elements) {
  		free(path->elements);
  	}
  	free(path);
  }
  
  static unsigned int vld_branch_find_last_element(vld_path *path)
  {
  	return path->elements[path->elements_count-1];
  }
  
  static int vld_path_exists(vld_path *path, unsigned int elem1, unsigned int elem2)
  {
  	unsigned int i;
  
  	for (i = 0; i < path->elements_count - 1; i++) {
  		if (path->elements[i] == elem1 && path->elements[i + 1] == elem2) {
  			return 1;
  		}
  	}
  	return 0;
  }
  
  static void vld_branch_find_path(unsigned int nr, vld_branch_info *branch_info, vld_path *prev_path)
  {
  	unsigned int last;
  	vld_path *new_path;
  	int found = 0;
  	size_t i = 0;
  
  	if (branch_info->paths_count > 255/*65535*/) {
  		return;
  	}
  
  	new_path = vld_path_new(prev_path);
  	vld_path_add(new_path, nr);
  
  	last = vld_branch_find_last_element(new_path);
  
  	for (i = 0; i < branch_info->branches[nr].outs_count; i++) {
  		int out = branch_info->branches[nr].outs[i];
  		if (out != 0 && out != VLD_JMP_EXIT && !vld_path_exists(new_path, last, out)) {
  			vld_branch_find_path(out, branch_info, new_path);
  			found = 1;
  		}
  	}
  	if (!found) {
  		vld_branch_info_add_path(branch_info, new_path);
  	} else {
  		vld_path_free(new_path);
  	}
  }
  
  void vld_branch_find_paths(vld_branch_info *branch_info)
  {
  	unsigned int i;
  
  	for (i = 0; i < branch_info->entry_points->size; i++) {
  		if (vld_set_in(branch_info->entry_points, i)) {
  			vld_branch_find_path(i, branch_info, NULL);
  		}
  	}
  }
  
  void vld_branch_info_dump(zend_op_array *opa, vld_branch_info *branch_info)
  {
  	unsigned int i, j;
  	const char *fname = opa->function_name ? ZSTRING_VALUE(opa->function_name) : "__main";
  
  	if (VLD_G(path_dump_file)) {
  		fprintf(VLD_G(path_dump_file), "subgraph cluster_%p {\n\tlabel=\"%s\";\n\tgraph [rankdir=\"LR\"];\n\tnode [shape = record];\n", opa, fname);
  
  		for (i = 0; i < branch_info->starts->size; i++) {
  			if (vld_set_in(branch_info->starts, i)) {
  				fprintf(
  					VLD_G(path_dump_file), 
  					"\t\"%s_%d\" [ label = \"{ op #%d-%d | line %d-%d }\" ];\n", 
  					fname, i, i, 
  					branch_info->branches[i].end_op,
  					branch_info->branches[i].start_lineno,
  					branch_info->branches[i].end_lineno
  				);
  				if (vld_set_in(branch_info->entry_points, i)) {
  					fprintf(VLD_G(path_dump_file), "\t%s_ENTRY -> %s_%d\n", fname, fname, i);
  				}
  				for (j = 0; j < branch_info->branches[i].outs_count; j++) {
  					if (branch_info->branches[i].outs[j]) {
  						if (branch_info->branches[i].outs[j] == VLD_JMP_EXIT) {
  							fprintf(VLD_G(path_dump_file), "\t%s_%d -> %s_EXIT;\n", fname, i, fname);
  						} else {
  							fprintf(VLD_G(path_dump_file), "\t%s_%d -> %s_%d;\n", fname, i, fname, branch_info->branches[i].outs[j]);
  						}
  					}
  				}
  			}
  		}
  		fprintf(VLD_G(path_dump_file), "}\n");
  	}
  
  	for (i = 0; i < branch_info->starts->size; i++) {
  		if (vld_set_in(branch_info->starts, i)) {
  			printf("branch: #%3d; line: %5d-%5d; sop: %5d; eop: %5d",
  				i,
  				branch_info->branches[i].start_lineno,
  				branch_info->branches[i].end_lineno,
  				i,
  				branch_info->branches[i].end_op
  			);
  
  			for (j = 0; j < branch_info->branches[i].outs_count; j++) {
  				if (branch_info->branches[i].outs[j]) {
  					printf("; out%d: %3d", j, branch_info->branches[i].outs[j]);
  				}
  			}
  			printf("\n");
  		}
  	}
  
  	for (i = 0; i < branch_info->paths_count; i++) {
  		printf("path #%d: ", i + 1);
  		for (j = 0; j < branch_info->paths[i]->elements_count; j++) {
  			printf("%d, ", branch_info->paths[i]->elements[j]);
  		}
  		printf("\n");
  	}
  }
  