#include <inc/stab.h>
#include <inc/string.h>
#include <inc/memlayout.h>
#include <inc/assert.h>
#include <inc/trap.h>

#include <kern/kdebug.h>
#include <kern/pmap.h>
#include <kern/env.h>

extern const struct Stab __STAB_BEGIN__[];	// Beginning of stabs table
extern const struct Stab __STAB_END__[];	// End of stabs table
extern const char __STABSTR_BEGIN__[];		// Beginning of string table
extern const char __STABSTR_END__[];		// End of string table

struct UserStabData {
	const struct Stab *stabs;
	const struct Stab *stab_end;
	const char *stabstr;
	const char *stabstr_end;
};


// stab_binsearch(stabs, region_left, region_right, type, addr)
//
//	Some stab types are arranged in increasing order by instruction
//	address.  For example, N_FUN stabs (stab entries with n_type ==
//	N_FUN), which mark functions, and N_SO stabs, which mark source files.
//
//	Given an instruction address, this function finds the single stab
//	entry of type 'type' that contains that address.
//
//	The search takes place within the range [*region_left, *region_right].
//	Thus, to search an entire set of N stabs, you might do:
//
//		left = 0;
//		right = N - 1;     /* rightmost stab */
//		stab_binsearch(stabs, &left, &right, type, addr);
//
//	The search modifies *region_left and *region_right to bracket the
//	'addr'.  *region_left points to the matching stab that contains
//	'addr', and *region_right points just before the next stab.  If
//	*region_left > *region_right, then 'addr' is not contained in any
//	matching stab.
//
//	For example, given these N_SO stabs:
//		Index  Type   Address
//		0      SO     f0100000
//		13     SO     f0100040
//		117    SO     f0100176
//		118    SO     f0100178
//		555    SO     f0100652
//		556    SO     f0100654
//		657    SO     f0100849
//	this code:
//		left = 0, right = 657;
//		stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184);
//	will exit setting left = 118, right = 554.
//
static void
stab_binsearch(const struct Stab *stabs, int *region_left, int *region_right,
	       int type, uintptr_t addr)
{
	int l = *region_left, r = *region_right, any_matches = 0;
	
	while (l <= r) {
		int true_m = (l + r) / 2, m = true_m;
		
		// search for earliest stab with right type
		while (m >= l && stabs[m].n_type != type)
			m--;
		if (m < l) {	// no match in [l, m]
			l = true_m + 1;
			continue;
		}

		// actual binary search
		any_matches = 1;
		if (stabs[m].n_value < addr) {
			*region_left = m;
			l = true_m + 1;
		} else if (stabs[m].n_value > addr) {
			*region_right = m - 1;
			r = m - 1;
		} else {
			// exact match for 'addr', but continue loop to find
			// *region_right
			*region_left = m;
			l = m;
			addr++;
		}
	}

	if (!any_matches)
		*region_right = *region_left - 1;
	else {
		// find rightmost region containing 'addr'
		for (l = *region_right;
		     l > *region_left && stabs[l].n_type != type;
		     l--)
			/* do nothing */;
		*region_left = l;
	}
}


// debuginfo_eip(addr, info)
//
//	Fill in the 'info' structure with information about the specified
//	instruction address, 'addr'.  Returns 0 if information was found, and
//	negative if not.  But even if it returns negative it has stored some
//	information into '*info'.
//
int
debuginfo_eip(uintptr_t addr, struct Eipdebuginfo *info)
{
	const struct Stab *stabs, *stab_end;
	const char *stabstr, *stabstr_end;
	int lfile, rfile, lfun, rfun, lline, rline;

	// Initialize *info
	info->eip_file = "<unknown>";
	info->eip_line = 0;
	info->eip_fn_name = "<unknown>";
	info->eip_fn_namelen = 9;
	info->eip_fn_addr = addr;
	info->eip_fn_narg = 0;

	// Find the relevant set of stabs
	if (addr >= ULIM) {
		stabs = __STAB_BEGIN__;
		stab_end = __STAB_END__;
		stabstr = __STABSTR_BEGIN__;
		stabstr_end = __STABSTR_END__;
	} else {
		// The user-application linker script, user/user.ld,
		// puts information about the application's stabs (equivalent
		// to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
		// __STABSTR_END__) in a structure located at virtual address
		// USTABDATA.
		const struct UserStabData *usd = (const struct UserStabData *) USTABDATA;

		// Make sure this memory is valid.
		// Return -1 if it is not.  Hint: Call user_mem_check.
		// LAB 3: Your code here.
		
		stabs = usd->stabs;
		stab_end = usd->stab_end;
		stabstr = usd->stabstr;
		stabstr_end = usd->stabstr_end;

		// Make sure the STABS and string table memory is valid.
		// LAB 3: Your code here.
	}

	// String table validity checks
	if (stabstr_end <= stabstr || stabstr_end[-1] != 0)
		return -1;

	// Now we find the right stabs that define the function containing
	// 'eip'.  First, we find the basic source file containing 'eip'.
	// Then, we look in that source file for the function.  Then we look
	// for the line number.
	
	// Search the entire set of stabs for the source file (type N_SO).
	lfile = 0;
	rfile = (stab_end - stabs) - 1;
	stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
	if (lfile == 0)
		return -1;

	// Search within that file's stabs for the function definition
	// (N_FUN).
	lfun = lfile;
	rfun = rfile;
	stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);

	if (lfun <= rfun) {
		// stabs[lfun] points to the function name
		// in the string table, but check bounds just in case.
		if (stabs[lfun].n_strx < stabstr_end - stabstr)
			info->eip_fn_name = stabstr + stabs[lfun].n_strx;
		info->eip_fn_addr = stabs[lfun].n_value;
		addr -= info->eip_fn_addr;
		// Search within the function definition for the line number.
		lline = lfun;
		rline = rfun;
	} else {
		// Couldn't find function stab!  Maybe we're in an assembly
		// file.  Search the whole file for the line number.
		info->eip_fn_addr = addr;
		lline = lfile;
		rline = rfile;
	}
	// Ignore stuff after the colon.
	info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name;

	
	// Search within [lline, rline] for the line number stab.
	// If found, set info->eip_line to the right line number.
	// If not found, return -1.
	//
	// Hint:
	//	There's a particular stabs type used for line numbers.
	//	Look at the STABS documentation and <inc/stab.h> to find
	//	which one.
	// Your code here.
	//cprintf("before my code\n");
	stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
    //cprintf("addr: %08x\nrline: %d\n",addr,rline);
    if(lline <= rline) {
        if ((addr >= stabs[rline-1].n_value)&&(addr < stabs[rline].n_value)) {
            info->eip_line = stabs[rline-1].n_desc;
            //cprintf("strx: %d\n",stabs[rline-1].n_strx);
        } else {
            info->eip_line = stabs[rline].n_desc;
            //cprintf("strx: %d\n",stabs[rline].n_strx);
        }
    } else {
	  return -1;
	}
	
	// Search backwards from the line number for the relevant filename
	// stab.
	// We can't just use the "lfile" stab because inlined functions
	// can interpolate code from a different file!
	// Such included source files use the N_SOL stab type.
	while (lline >= lfile
	       && stabs[lline].n_type != N_SOL
	       && (stabs[lline].n_type != N_SO || !stabs[lline].n_value))
		lline--;
	if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr)
		info->eip_file = stabstr + stabs[lline].n_strx;


	// Set eip_fn_narg to the number of arguments taken by the function,
	// or 0 if there was no containing function.
	// Your code here.

	
	return 0;
}
\
//returns 1 if the variable with name is found in the line index of the stabs, otherwise 0
bool found_var(char *name, int index, uintptr_t addr, int type) {
	const char * stabstr;
	const char * stab_string;
	unsigned int i;
	const struct Stab *stabs;
	
	if (!( (type == N_LSYM) || (type == N_RSYM) || (type == N_PSYM) )) {
		return 0;
	}

	//cprintf("\n [index %d] local variable: ", index);

	// Find the relevant set of stabs
	if (addr >= ULIM) {
		stabs = __STAB_BEGIN__;		
		stabstr = __STABSTR_BEGIN__;
		
	} else {
		// The user-application linker script, user/user.ld,
		// puts information about the application's stabs (equivalent
		// to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
		// __STABSTR_END__) in a structure located at virtual address
		// USTABDATA.
		const struct UserStabData *usd = (const struct UserStabData *) USTABDATA;
	
		stabs = usd->stabs;

		stabstr = usd->stabstr;
	}


	stab_string = stabstr + stabs[index].n_strx;
	
	for (i = 0 ; i < strlen(name); i++) {
		//cprintf("%c", stab_string[i]);
		if (stab_string[i] == ':') {
			return 0;
		}
		if (name[i] != stab_string[i]) {
			return 0;	
		}
	}
	return 1;
}


void
print_r(struct PushRegs *regs)
{
	cprintf("  edi  0x%08x\n", regs->reg_edi);
	cprintf("  esi  0x%08x\n", regs->reg_esi);
	cprintf("  ebp  0x%08x\n", regs->reg_ebp);
	cprintf("  oesp 0x%08x\n", regs->reg_oesp);
	cprintf("  ebx  0x%08x\n", regs->reg_ebx);
	cprintf("  edx  0x%08x\n", regs->reg_edx);
	cprintf("  ecx  0x%08x\n", regs->reg_ecx);
	cprintf("  eax  0x%08x\n", regs->reg_eax);
}



// eip = the return address of the current function
// name = the name of the variable we would like to locate -- it must be a local variable
//returns the virtual address 
// returns NULL if variable name is not found 
uint32_t set_addr(char * name, struct Trapframe * tf, uint32_t value) {
	//cprintf("variable name: %s size  %d\n",name, strlen(name));
	uintptr_t addr;
	int lfun, rfun, lfile, rfile;
	const struct Stab *stabs;
	const struct Stab *stab_end;
	struct Eipdebuginfo info;
	


    
	addr = (uint32_t) (tf->tf_eip);
	//cprintf("addr given is %08x and name %s \n", addr, name);

// Find the relevant set of stabs
	if (addr >= ULIM) {
		cprintf("address is above ULIM\n");
		stabs = __STAB_BEGIN__;
		stab_end = __STAB_END__;
		
	} else {
		// The user-application linker script, user/user.ld,
		// puts information about the application's stabs (equivalent
		// to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
		// __STABSTR_END__) in a structure located at virtual address
		// USTABDATA.
		const struct UserStabData *usd = (const struct UserStabData *) USTABDATA;
	
		stabs = usd->stabs;
		stab_end = usd->stab_end;


	}

	// Now we find the right stabs that define the function containing
	// 'eip'.  First, we find the basic source file containing 'eip'.
	// Then, we look in that source file for the function.  Then we look
	// for the line number.
	
	// Search the entire set of stabs for the source file (type N_SO).
	lfile = 0;
	rfile = (stab_end - stabs) - 1;
	stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
	if (lfile == 0) {
		cprintf("could not find source file\n");
		return 0;
	}
	//cprintf("source file start is bracketed at lfile %d  rfile %d \n", lfile, rfile);
	// Search within that file's stabs for the function definition
	// (N_FUN).
	lfun = lfile;
	rfun = rfile;
	stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);

//ERASE
if (debuginfo_eip(addr, &info) < 0) {
	
	//cprintf("error with debug eip \n");
	
} else {
	//cprintf("function name is %s \n", info.eip_fn_name);
}
	if (lfun > rfun) {
		cprintf("Couldn't find the function that has the local var  \n");
		return 0;
	}
	//cprintf("lfun %d and rfun %d should bracket ls are\n", lfun, rfun);
	lfun++;
	//go through stabs until found character of another function
	while ((stabs[lfun].n_type != N_FUN) && (!(found_var(name, lfun, addr,stabs[lfun].n_type))) && (lfun < (stab_end - stabs) - 1)) {		
		lfun++;
	}

	if ((stabs[lfun].n_type == N_FUN)  || (lfun >= (stab_end - stabs) -1)){
		//did not find the variable through the stabs
		cprintf("did not find the local variable\n");
		return 0;
	}
	//cprintf("found variable at index %d and putting value %d \n", lfun, value);
	//cprintf("nvalue of mine %x, of previous %x, of next %x \n", stabs[lfun].n_value, stabs[lfun-1].n_value, stabs[lfun+1].n_value);
	//cprintf("desc of mine %x, of previous %x, of next %x \n", stabs[lfun].n_desc, stabs[lfun-1].n_desc, stabs[lfun+1].n_desc);s
	if (stabs[lfun].n_type == N_RSYM) {
		//cprintf("RSYM: n_value is %08x \n", stabs[lfun].n_value);
		//cprintf("eax %08x,\n %ebx %08x, \n %ecx %08x \n %edx %08x \n", tf->tf_regs.reg_eax,tf->tf_regs.reg_ebx, tf->tf_regs.reg_ecx, tf->tf_regs.reg_edx );
		//cprintf("esi %08x,\n %edi %08x \n", tf->tf_regs.reg_esi,tf->tf_regs.reg_edi );
		//cprintf("the trapframe is : \n");
		//print_r(&(tf->tf_regs));
		switch (stabs[lfun].n_value) {
        case 3: {tf->tf_regs.reg_ebx = value;
                cprintf("%s = %d \n", name, value);
                break;}
        case 4: {tf->tf_regs.reg_ecx = value;
                cprintf("%s = %d \n", name, value);
                break;}
        default : {cprintf("var not found");}    
        }
		return 0; 

	}
	if (stabs[lfun].n_type == N_LSYM) {
		//cprintf("LSYM");
		addr = tf->tf_regs.reg_ebp + stabs[lfun].n_value;
		
	//cprintf("address returned is %08x and ebp is %08x \n ", addr, tf->tf_regs.reg_ebp);
		
	   return (uint32_t)addr;
	}

	if (stabs[lfun].n_type == N_PSYM) {
		cprintf("parameter variables not supported\n");
	}

	return 0;
	

}

// eip = the return address of the current function
// name = the name of the variable we would like to locate -- it must be a local variable
//returns the virtual address 
// returns NULL if variable name is not found 
uint32_t var_addr(char * name, struct Trapframe * tf) {
	//cprintf("variable name: %s size  %d\n",name, strlen(name));
	uintptr_t addr;
	int lfun, rfun, lfile, rfile;
	const struct Stab *stabs;
	const struct Stab *stab_end;
	struct Eipdebuginfo info;
	


    
	addr = (uint32_t) (tf->tf_eip);
	//cprintf("addr given is %08x \n", addr);

// Find the relevant set of stabs
	if (addr >= ULIM) {
		cprintf("address is above ULIM\n");
		stabs = __STAB_BEGIN__;
		stab_end = __STAB_END__;
		
	} else {
		// The user-application linker script, user/user.ld,
		// puts information about the application's stabs (equivalent
		// to __STAB_BEGIN__, __STAB_END__, __STABSTR_BEGIN__, and
		// __STABSTR_END__) in a structure located at virtual address
		// USTABDATA.
		const struct UserStabData *usd = (const struct UserStabData *) USTABDATA;
	
		stabs = usd->stabs;
		stab_end = usd->stab_end;


	}

	// Now we find the right stabs that define the function containing
	// 'eip'.  First, we find the basic source file containing 'eip'.
	// Then, we look in that source file for the function.  Then we look
	// for the line number.
	
	// Search the entire set of stabs for the source file (type N_SO).
	lfile = 0;
	rfile = (stab_end - stabs) - 1;
	stab_binsearch(stabs, &lfile, &rfile, N_SO, addr);
	if (lfile == 0) {
		cprintf("could not find source file\n");
		return 0;
	}
	//cprintf("source file start is bracketed at lfile %d  rfile %d \n", lfile, rfile);
	// Search within that file's stabs for the function definition
	// (N_FUN).
	lfun = lfile;
	rfun = rfile;
	stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr);

//ERASE
if (debuginfo_eip(addr, &info) < 0) {
	
	//cprintf("error with debug eip \n");
	
} else {
	//cprintf("function name is %s \n", info.eip_fn_name);
}
	if (lfun > rfun) {
		cprintf("Couldn't find the function that has the local var  \n");
		return 0;
	}
	//cprintf("lfun %d and rfun %d should bracket ls are\n", lfun, rfun);
	lfun++;
	//go through stabs until found character of another function
	while ((stabs[lfun].n_type != N_FUN) && (!(found_var(name, lfun, addr,stabs[lfun].n_type))) && (lfun < (stab_end - stabs) - 1)) {		
		lfun++;
	}

	if ((stabs[lfun].n_type == N_FUN)  || (lfun >= (stab_end - stabs) -1)){
		//did not find the variable through the stabs
		cprintf("did not find the local variable\n");
		return 0;
	}
	//cprintf("found variable at index %d \n", lfun);
	//cprintf("nvalue of mine %x, of previous %x, of next %x \n", stabs[lfun].n_value, stabs[lfun-1].n_value, stabs[lfun+1].n_value);
	//cprintf("desc of mine %x, of previous %x, of next %x \n", stabs[lfun].n_desc, stabs[lfun-1].n_desc, stabs[lfun+1].n_desc);
	if (stabs[lfun].n_type == N_RSYM) {
		//cprintf("RSYM: n_value is %08x \n", stabs[lfun].n_value);
		//cprintf("eax %08x,\n %ebx %08x, \n %ecx %08x \n %edx %08x \n", tf->tf_regs.reg_eax,tf->tf_regs.reg_ebx, tf->tf_regs.reg_ecx, tf->tf_regs.reg_edx );
		//cprintf("esi %08x,\n %edi %08x \n", tf->tf_regs.reg_esi,tf->tf_regs.reg_edi );
		//cprintf("trapframe is : \n");
		//print_r(&(tf->tf_regs));
		switch (stabs[lfun].n_value) {
        case 3: {cprintf("%s = %d \n", name, tf->tf_regs.reg_ebx); 
                break;}
        case 4: {cprintf( "%s = %d \n", name, tf->tf_regs.reg_ecx); 
                break;}
        default: {cprintf("var not found");}
        }

        return 0; 

	}
	if (stabs[lfun].n_type == N_LSYM) {
		//cprintf("LSYM: %d\n",stabs[lfun].n_value);
		addr = tf->tf_regs.reg_ebp + stabs[lfun].n_value;
		
	//cprintf("address returned is %08x and ebp is %08x \n ", addr, tf->tf_regs.reg_ebp);
		
	return (uint32_t)addr;
	}

	if (stabs[lfun].n_type == N_PSYM) {
		cprintf("parameter variables not supported\n");
	}

	return 0;
	

}