Addition of Control Flow Graph related implementation.
[dyninst.git] / dyninstAPI / src / LineInformation.C
1 #include <stdlib.h>
2
3 #include "dyninstAPI/src/LineInformation.h"
4 #include "dyninstAPI/src/util.h"
5
6 typedef FileLineInformation::tuple tuple;
7
8 //this function implements binary search and returns the found element.
9 //besides the found element it returns the next bigger line numbered one
10 //The found element is the first same values element in the array in existence
11 //of many same values elements.
12 //in case it is not found it will RETURN NULL. if the next element
13 //is not available it will assign NULL to the reference.
14 //the next contains the entry with the first greater line number
15 tuple* binarySearchLineFirst(tuple element,tuple* array,int howMany,tuple*& next)
16 {
17         int low = 0;
18         int high = howMany-1;
19         int mid;
20         tuple* ret=NULL;
21         do{
22                 mid = (low+high)/2;
23                 if(element.lineNo < array[mid].lineNo) 
24                         high = mid - 1;
25                 else if(element.lineNo > array[mid].lineNo)
26                         low = mid + 1;
27                 else
28                         break;
29         }while(low <= high);
30
31         //if found then porepare to return and the next available
32         if(element.lineNo == array[mid].lineNo){
33                 int index = mid;
34                 for(;(index >= 0)&&(array[index].lineNo == element.lineNo);index--);
35                 ret = array+(index+1);
36                 index = mid;
37                 for(;(index < howMany)&&(array[index].lineNo == element.lineNo);index++);
38                 if(index == howMany)
39                         next = NULL;
40                 else
41                         next = array+index;
42         }
43         else if(low == howMany)
44                 next = NULL;
45         else
46                 next = array+low;
47
48         return ret;
49 }
50 //this function implements binary search and returns the found element.
51 //besides the found element it returns the previous smaller address entry
52 //The found element is the first same values element in the array in existence
53 //of many same values elements.
54 //in case it is not found it will RETURN NULL. if the next element
55 //is not available it will assign NULL to the reference.
56 //the next contains the entry with the previous smaller address
57 tuple* binarySearchAddrFirst(tuple element,tuple* array,int howMany,tuple*& next)
58 {
59         int low = 0;
60         int high = howMany-1;
61         int mid;
62         tuple* ret=NULL;
63         do{
64                 mid = (low+high)/2;
65                 if(element.codeAddress < array[mid].codeAddress) 
66                         high = mid - 1;
67                 else if(element.codeAddress > array[mid].codeAddress)
68                         low = mid + 1;
69                 else
70                         break;
71         }while(low <= high);
72
73         ////if found then porepare to return and the next available
74         if(element.codeAddress == array[mid].codeAddress){
75                 int index = mid;
76                 for(;(index>=0)&&(array[index].codeAddress == element.codeAddress);index--);
77                 ret = array+(index+1);
78                 if(index == -1)
79                         next = NULL;
80                 else{
81                         Address addr = array[index].codeAddress;
82                         for(;(index>=0) && (array[index].codeAddress == addr);index--);
83                         next = array+(index+1);
84                 }
85         }
86         else if(high == -1)
87                 next = NULL;
88         else{
89                 Address addr = array[high].codeAddress;
90                 for(;(high >=0) && (array[high].codeAddress == addr);high--);
91                 next = array+(high+1);
92         }
93         return ret;
94 }
95
96 //constructor
97 FileLineInformation::FileLineInformation(string fileName)
98         : sourceFileName(fileName),
99           size(0),
100           lineToAddr(NULL),
101           addrToLine(NULL),
102           functionCount(0),
103           functionNameList(NULL),
104           lineInformationList(NULL) {}
105
106 //destructor
107 FileLineInformation::~FileLineInformation(){
108         delete[] lineToAddr;
109         delete[] addrToLine;
110         for(int i=0;i<functionCount;i++){
111                 delete lineInformationList[i];
112                 delete functionNameList[i];
113         }
114         delete[] functionNameList;
115         delete[] lineInformationList;
116 }
117
118 //returns the function info structure
119 FileLineInformation::FunctionInfo* 
120 FileLineInformation::findFunctionInfo(string functionName){
121         for(int i=0;i<functionCount;i++)
122                 if(functionName == *functionNameList[i])
123                         return lineInformationList[i];
124         return NULL;
125 }
126
127 //inserts function wntry to the mapping from function name to its info
128 void FileLineInformation::insertFunction(string functionName){
129         FunctionInfo* fInfo = findFunctionInfo(functionName);
130         if(!fInfo){
131                 functionNameList = (string**)(functionCount ? 
132                         realloc(functionNameList,(functionCount+1)*sizeof(string*)) : 
133                         new string*[1]);
134                 lineInformationList = (FunctionInfo**)(functionCount ? 
135                         realloc(lineInformationList,(functionCount+1)*sizeof(FunctionInfo*)) : 
136                         new FunctionInfo*[1]);
137                 functionNameList[functionCount] = new string(functionName);
138                 lineInformationList[functionCount] = new FunctionInfo;
139                 functionCount++;
140         }       
141 }
142
143 //returns true if the function has an entry in the mapping
144 bool FileLineInformation::findFunction(string functionName){
145         FunctionInfo* fInfo = findFunctionInfo(functionName);
146         if(!fInfo) return false;
147         return true;
148 }
149
150
151 //insert a mapping from line number to address and address to line number
152 //to the corresponding structures and updates the records for the function
153 //given
154 void FileLineInformation::insertLineAddress(string functionName,
155                                             unsigned short lineNo,
156                                             Address codeAddress)
157 {
158
159         FunctionInfo* fInfo = findFunctionInfo(functionName);
160         if(!fInfo){
161                 cerr << "FATAL ERROR : Something wrong \n";
162                 return;
163         }
164
165         lineToAddr = !lineToAddr ? ((tuple*)malloc(sizeof(tuple))) :
166                      ((tuple*)realloc(lineToAddr,sizeof(tuple)*(size+1)));
167         addrToLine = !addrToLine ? ((tuple*)malloc(sizeof(tuple))) :
168                      ((tuple*)realloc(addrToLine,sizeof(tuple)*(size+1)));
169
170         //since the entries will come in oreder insertion sort is the best sort here
171         //to keep the list sorted and using binary search to find the entries.
172         //insertion sort comes here
173
174         short index1; 
175         for(index1=size-1;index1>=0;index1--)
176                 if(lineToAddr[index1].lineNo > lineNo)
177                         lineToAddr[index1+1] = lineToAddr[index1];
178                 else break;
179         index1++;
180         lineToAddr[index1] = tuple(lineNo,codeAddress);
181
182         short index2; 
183         //insertion sort for code address
184
185         for(index2=size-1;index2>=0;index2--)
186                 if(addrToLine[index2].codeAddress > codeAddress)
187                         addrToLine[index2+1] = addrToLine[index2];
188                 else break;
189         index2++;
190         addrToLine[index2] = tuple(lineNo,codeAddress);
191
192         size++;
193
194         if(!fInfo->validInfo){
195                 fInfo->startLinePtr = (unsigned)index1;
196                 fInfo->endLinePtr = (unsigned)index1;
197                 fInfo->startAddrPtr = (unsigned)index2;
198                 fInfo->endAddrPtr = (unsigned)index2;
199                 fInfo->validInfo = true;
200                 return;
201         }
202
203         if(lineToAddr[fInfo->startLinePtr].lineNo > lineNo)
204                 fInfo->startLinePtr = (unsigned)index1;
205         if(lineToAddr[fInfo->endLinePtr].lineNo <= lineNo)
206                 fInfo->endLinePtr = (unsigned)index1;
207
208         if(addrToLine[fInfo->startAddrPtr].codeAddress > codeAddress)
209                 fInfo->startAddrPtr = (unsigned)index2;
210         if(addrToLine[fInfo->endAddrPtr].codeAddress <= codeAddress)
211                 fInfo->endAddrPtr = (unsigned)index2;
212
213 }
214  
215 //returns true in case of success, false otherwise.
216 //this method finds the line number corresponding to an address.
217 //if name of the function is supplied and isFile is false
218 //then function level search is being applied. Otherwise file level
219 //search is applied. If there are more than 1 line found than
220 //the maximum is being returned.
221 bool FileLineInformation::getLineFromAddr(string name,unsigned short& lineNo,
222                                           Address codeAddress,bool isFile,
223                                           bool isExactMatch)
224 {
225         BPatch_Set<unsigned short> lines;
226         if(!getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch))
227                 return false;
228         lineNo = lines.maximum();
229         return true;
230 }
231 //returns true in case of success, false otherwise.
232 //this method finds the line numbers corresponding to an address.
233 //if name of the function is supplied and isFile is false
234 //then function level search is being applied. Otherwise file level
235 //search is applied. All the line numbers corresponding to the address
236 //is returned in a set of addresses.
237 bool FileLineInformation::getLineFromAddr(string name,
238                                           BPatch_Set<unsigned short>& lines,
239                                           Address codeAddress,bool isFile,
240                                           bool isExactMatch)
241 {
242         tuple* beginPtr;
243         tuple* endPtr;
244         int howMany;
245
246         if(!addrToLine)
247                 return false;
248         if(isFile){
249                 beginPtr = addrToLine;
250                 endPtr = (tuple*) (addrToLine+(size-1));
251                 howMany = size;
252         }
253         else{
254                 FunctionInfo* fInfo = findFunctionInfo(name);
255                 if(!fInfo)
256                         return false;
257                 if(!fInfo->validInfo)
258                         return false;
259                 beginPtr = addrToLine+fInfo->startAddrPtr;
260                 endPtr = addrToLine+fInfo->endAddrPtr;
261                 howMany = fInfo->endAddrPtr-fInfo->startAddrPtr+1;
262         }
263
264         if((codeAddress < beginPtr->codeAddress) || (endPtr->codeAddress < codeAddress))
265                 return false;
266
267         tuple toSearch(0,codeAddress);
268         tuple* next=NULL;
269         tuple* ret = binarySearchAddrFirst(toSearch,beginPtr,howMany,next);
270         if(!ret){
271                 if(isExactMatch)
272                         return false;
273                 if(!next)
274                         return false;
275                 ret = next;
276                 codeAddress = ret->codeAddress;
277         }
278         do{
279                 lines += ret->lineNo;
280                 ret++;
281         }while((ret <= endPtr) && (ret->codeAddress == codeAddress));
282
283         return true;
284 }
285
286 //method that retuns set of addresses corresponding to a given line number
287 //the level of the search is file level if isFile flag is set.
288 //If isFile level is not set, it seraches in the given function
289 //in case of success it returns true otherwise false
290 bool FileLineInformation::getAddrFromLine(string name,
291                                           BPatch_Set<Address>& codeAddress,
292                                           unsigned short lineNo,bool isFile,
293                                           bool isExactMatch)
294 {
295         tuple* beginPtr;
296         tuple* endPtr;
297         int howMany;
298
299         if(!lineToAddr)
300                 return false;
301         if(isFile){
302                 beginPtr = lineToAddr;
303                 endPtr = (tuple*) (lineToAddr+(size-1));
304                 howMany = size;
305         }
306         else{
307                 FunctionInfo* fInfo = findFunctionInfo(name);
308                 if(!fInfo)
309                         return false;
310                 if(!fInfo->validInfo)
311                         return false;
312                 beginPtr = lineToAddr+fInfo->startLinePtr;
313                 endPtr = lineToAddr+fInfo->endLinePtr;
314                 howMany = fInfo->endLinePtr-fInfo->startLinePtr+1;
315         }
316         if(!isFile && 
317            (lineNo < beginPtr->lineNo) || (endPtr->lineNo < lineNo))
318                 return false;
319
320         tuple toSearch(lineNo,0);
321         tuple* next=NULL;
322         tuple* ret = binarySearchLineFirst(toSearch,beginPtr,howMany,next);
323         if(!ret){
324                 if(isExactMatch)
325                         return false;
326                 if(!next)
327                         return false;
328                 ret = next;
329                 lineNo = ret->lineNo;
330         }
331         do{
332                 codeAddress += ret->codeAddress;
333                 ret++;
334         }while((ret <= endPtr) && (ret->lineNo == lineNo));
335
336         return true;
337 }
338
339 //constructor whose argument is the name of the module name
340 LineInformation::LineInformation(string mName) 
341                 : moduleName(mName),
342                   sourceFileCount(0),
343                   sourceFileList(NULL),
344                   lineInformationList(NULL) {}
345
346
347 //desctructor
348 LineInformation::~LineInformation() {
349         for(int i=0;i<sourceFileCount;i++){
350                 delete sourceFileList[i];
351                 delete lineInformationList[i];
352         }
353         delete[] sourceFileList;
354         delete[] lineInformationList;
355 }
356
357 //method to insert entries for the given file name and function name
358 //it creates the necessary structures and inserts into the maps
359 void LineInformation::insertSourceFileName(string functionName,string fileName)
360 {
361         FileLineInformation* fInfo = getFileLineInformation(fileName);
362         if(!fInfo){
363                 fInfo = new FileLineInformation(fileName);
364                 sourceFileList = (string**)(sourceFileCount ? 
365                         realloc(sourceFileList,(sourceFileCount+1)*sizeof(string*)) : 
366                         new string*[1]);
367                 lineInformationList = (FileLineInformation**)(sourceFileCount ? 
368                         realloc(lineInformationList,(sourceFileCount+1)*sizeof(FileLineInformation*)) : 
369                         new FileLineInformation*[1]);
370                 sourceFileList[sourceFileCount] = new string(fileName);
371                 lineInformationList[sourceFileCount] = fInfo;
372                 sourceFileCount++;
373         }
374         fInfo->insertFunction(functionName);
375 }
376
377 //inserts line to address and address to line mapping to the line info
378 //object of the given filename. The records for function is also updated
379 void LineInformation::insertLineAddress(string functionName,
380                                         string fileName,
381                                         unsigned short lineNo,
382                                         Address codeAddress)
383 {
384         FileLineInformation* fInfo = getFileLineInformation(fileName);
385         if(!fInfo) return;
386         fInfo->insertLineAddress(functionName,lineNo,codeAddress);
387 }
388
389 //returns line number corresponding to the the given address
390 //if isFile is set the search is file level otherwsie function level.
391 bool LineInformation::getLineFromAddr(string name,
392                                       unsigned short& lineNo,
393                                       Address codeAddress,
394                                       bool isFile,
395                                       bool isExactMatch)
396 {
397         FileLineInformation* fInfo = NULL;
398         if(isFile) 
399                 fInfo = getFileLineInformation(name);
400         else
401                 fInfo = getFunctionLineInformation(name);
402                 
403         if(!fInfo) return false;
404         
405         return fInfo->getLineFromAddr(name,lineNo,codeAddress,isFile,isExactMatch);
406 }
407
408 //returns line number corresponding to the the given address
409 //if isFile is set the search is file level otherwsie function level.
410 bool LineInformation::getLineFromAddr(string name,
411                                       BPatch_Set<unsigned short>& lines,
412                                       Address codeAddress,
413                                       bool isFile,
414                                       bool isExactMatch)
415 {
416         FileLineInformation* fInfo = NULL;
417         if(isFile) 
418                 fInfo = getFileLineInformation(name);
419         else
420                 fInfo = getFunctionLineInformation(name);
421                 
422         if(!fInfo) return false;
423         
424         return fInfo->getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch);
425 }
426
427 //returns address corresponding to the the given line 
428 //if isFile is set the search is file level otherwsie function level.
429 bool LineInformation::getAddrFromLine(string name,
430                                       BPatch_Set<Address>& codeAddress,
431                                       unsigned short lineNo,
432                                       bool isFile,
433                                       bool isExactMatch)
434 {
435         FileLineInformation* fInfo = NULL;
436         if(isFile) 
437                 fInfo = getFileLineInformation(name);
438         else
439                 fInfo = getFunctionLineInformation(name);
440                 
441         if(!fInfo) return false;
442
443         return fInfo->getAddrFromLine(name,codeAddress,lineNo,isFile,isExactMatch);
444 }
445
446 bool LineInformation::getAddrFromLine(BPatch_Set<Address>& codeAddress,
447                                       unsigned short lineNo,
448                                       bool isExactMatch)
449 {
450         FileLineInformation* fInfo = getFileLineInformation(moduleName);
451         if(!fInfo){ 
452 #ifdef DEBUG_LINE
453                 cerr << "Module " << moduleName << " is not source file name\n";
454 #endif
455                 return false;
456         }
457         return fInfo->getAddrFromLine(moduleName,codeAddress,
458                                       lineNo,true,isExactMatch);
459 }
460
461 //returns the line information for the given filename
462 FileLineInformation* LineInformation::getFileLineInformation(string fileName){
463         for(int j=0;j<sourceFileCount;j++)
464                 if(fileName == *sourceFileList[j])
465                         return lineInformationList[j];
466         for(int i=0;i<sourceFileCount;i++){
467                 char* name = new char[sourceFileList[i]->length()+1];
468                 strncpy(name,sourceFileList[i]->string_of(),
469                         sourceFileList[i]->length());
470                 name[sourceFileList[i]->length()] = '\0';
471                 char* p = strrchr(name,'/');
472                 if(!p) {
473                         delete[] name;
474                         continue;
475                 }
476                 p++;
477                 string sname(p);
478                 if(fileName == sname){
479                         delete[] name;
480                         return lineInformationList[i];
481                 }
482                 delete[] name;
483         }
484                 
485         return NULL;
486
487
488 //method retuns the file line information object which the function belongs to.
489 //if there is no entry than it retuns NULL
490 FileLineInformation* 
491 LineInformation::getFunctionLineInformation(string functionName){
492         for(int i=0;i<sourceFileCount;i++)
493                 if(lineInformationList[i]->findFunction(functionName))
494                         return lineInformationList[i];
495         return NULL;
496
497
498 //method that returns true if function belongs to this object
499 //false otherwise
500 bool LineInformation::findFunction(string functionName){
501         bool ret = false;
502         for(int i=0;!ret && (i<sourceFileCount);i++)
503                 ret = lineInformationList[i]->findFunction(functionName);
504         return ret;
505 }
506
507 ostream& operator<<(ostream& os,FileLineInformation& linfo){
508
509         cerr << "LINE TO ADDRESS :\n";
510         for(int j=0;j<linfo.size;j++){
511                 os << dec << linfo.lineToAddr[j].lineNo << " ----> ";
512                 os << hex << linfo.lineToAddr[j].codeAddress << "\n";
513         }
514         for(int i=0;i<linfo.functionCount;i++){
515                 FileLineInformation::FunctionInfo* funcinfo = 
516                                 linfo.lineInformationList[i];
517                 os << "FUNCTION LINE : " << *(linfo.functionNameList[i]) << " : " ;
518                 if(!funcinfo->validInfo)
519                         continue;
520                 os << dec << linfo.lineToAddr[funcinfo->startLinePtr].lineNo << " --- ";
521                 os << dec << linfo.lineToAddr[funcinfo->endLinePtr].lineNo << "\n";
522         }
523         return os;
524         
525 }
526
527 ostream& operator<<(ostream& os,LineInformation& linfo){
528         os << "**********************************************\n";
529         os << "MODULE : " << linfo.moduleName << "\n";  
530         os << "**********************************************\n";
531         for(int i=0;i<linfo.sourceFileCount;i++){
532                 os << "FILE : " << *(linfo.sourceFileList[i]) << "\n";
533                 os << *(linfo.lineInformationList[i]);
534         }
535         return os;
536 }
537