Extracting Functions,Globals,Constants,etc

Robert

Hi, I wrote a utility to scan a source file and identify required modules. Part of this program involved scanning a .bmx source file and making a list of all the symbols it contained (ie. funcs, globals, types, methods etc.)

This may not be complete for your needs. The relevant stuff begins with the extractSymbols function in modscanner.bmx (the main source file)

modscanner.bmx

'Title:  ModScanner
'Author: Robert Knight
'============================
'ModScanner is a utility which examines a given BlitzMAX source file and produces
'a list of the modules required to build that source file, plus relevant additional modules
'that may be needed at runtime.
'
'ModScanner works by scanning the contents of the BlitzMAX module source folder, and building
'a list of symbols (types,globals,methods,functions and constants) found in each one.
'The list of symbols is stored in a file called symbols.cache for easier loading in future.
'
'ModScanner then examines the BlitzMAX source file specified to produce a list of required 
'functions and types, which it then checks against the big symbol list.

'Usage:
'
'  Compile & run the modscanner source.  On first run you will need to enter the
'  path to your BlitzMAX module directory (eg:  C:\BlitzMAX\mod).
'  Select the source file to analyse from the box that appears and click OK.
'
'  To clear modscanner's data cache and settings, delete the symbols.files.cache and 
'  modscanner.cfg files which the program automatically creates.
'
'History:
'
'  - Alpha 4 - Tidied the program up so that each source file is now only scanned once
'              to determine required symbols.
'            - Added exception handling to deal with cache corruption or deletion.
'  - Alpha 3 - Redundant items are now removed from the outputed module list
'			  (eg. If BRL.Max2D and BRL.LinkedList are required, BRL.LinkedList
'			   will be removed since Max2D imports it anyway)
'  - Alpha 2 - Added support for scanning Imported and Included source files
'            - Reworked the cache system to improve performance 
'  - Alpha 1 - First Release
'
'Limitations:
'  - ModScanner cannot identify required constants or globals in the specified source file
'  - ModScanner doesn't automatically rebuild the cache if new source files are added to the 
'    module folder, it only spots changes if an existing file is modified 
'    (although the rebuild will spot any new source files)
'  - The list of additional modules which ModScanner may suggest importing is currently
'    hardcoded, the only way to change it is to play with the source code.
'  - ModScanner doesn't know about Public vs Private types and functions.

'Other notes:  ModScanner needs read access to the modules folder and write access to the folder
'where it is currently located so that it can store the symbols cache.

'Have fun :) - Feedback to robertknight@...   


Strict

Framework BRL.System
Import BRL.Retro

Import "map.bmx"

Const NUM_START=48
Const NUM_END=57
Const LOWER_START=97
Const LOWER_END=122
Const UPPER_START=65
Const UPPER_END=90
Const UNDERSCORE=95

Const MOD_PNG:String="'Import brl.pngloader  '--Uncomment to add support for PNG Images"
Const MOD_BMP:String="'Import brl.bmploader  '--Uncomment to add support for BMP Images"
Const MOD_JPG:String="'Import brl.jpgloader  '--Uncomment to add support for JPEG Images"
Const MOD_TGA:String="'Import brl.tgaloader  '--Uncomment to add support for TGA Images"
Const MOD_GL:String="'Import brl.glmax2d  '--Uncomment to add support for OpenGL-powered 2D (recommended)"
Const MOD_FREEAUDIO:String="'Import brl.freeaudioaudio  '--Uncomment to enable Blitz Research audio (recommended)"
Const MOD_FREETYPE:String="'Import brl.freetypefont  '--Uncomment to enable font commands"
Const MOD_OGG:String="'Import brl.oggloader  '--Uncomment to add support for OGG format music"
Const MOD_WAV:String="'Import brl.wavloader  '--Uncomment to add support for WAV format sound"
Const MOD_HTTPSTREAM:String="'Import brl.httpstream  '--Uncomment to add support for web-based streams"
Const MOD_TCPSTREAM:String="'Import brl.socketstream  '--Uncomment to add support for TCP/IP streams"

Const VERSION:String="Alpha 1"

Global BMAX_KEYWORDS:String[]=[	"strict","module","moduleinfo","framework",..
							"end","return","continue","exit","assert","flushmem",..
							"public","private","true","false","pi","null","self","super",..
							"byte","short","int","long","float","double","object","string",..
							"var","ptr","varptr","chr","len","asc","sizeof","sgn","abs",..
							"min","max","mod","shl","shr","sar","not","and","or","new",..
							"release","delete","incbin","incbinptr","incbinlen","include",..
							"import","extern","endextern","function","endfunction","type",..
							"endtype","extends","method","endmethod","local","global",..
							"const","field","abstract","final","rem","endrem","if","then",..
							"else","elseif","endif","for","to","next","eachin","step",..
							"while","wend","repeat","until","forever","select","case",..
							"default","endselect","try","throw","catch","endtry","goto",..
							"defdata","readdata","restoredata","alias"]
				
'List of keywords - if a symbol which the program thinks might be a function or type is found in this list
'then modscanner knows it won't need to search the big scary binary tree containing all the functions
'and types etc. found in the modules folder			
Global keywordsList=ListFromArray(BMAX_KEYWORDS)

'Create a list of all of the BlitzMAX source files found in the modules folder
Local modFiles:TList=New TList

Global modSourceFolder:String=getModSourceFolder()

Print "Scanning "+modSourceFolder+"..."
addFolderContentsToList(modSourceFolder,modFiles,["bmx"])


'Ask the user which source file they want to analyse, then work out which source files it depends on,
'(ie. look for Import and Include statements)
Local path:String=RequestFile(Null)
If Not path End

Local paths:TList=New TList

scanForImports(path,paths)
paths.AddFirst(path)

Local startTime=MilliSecs()

'Load the big list of symbols defined in the BlitzMAX source files in the modules folder
Local symbols:Map=loadSymbols(modFiles)

Local scanStartTime=MilliSecs()

Print "Scanning "+StripDir(path)+" and imports..."
Print Null

Local isFirstFile=True  'Only the main source file needs a 'FrameWork' statement

'Scan through each source file to identify the functions and types it needs in order to compile, then search
'for matches in the big symbol tree.
For Local path:String=EachIn paths

	Local requiredSymbols:Map=findRequiredSymbols(path)
	
	FlushMem

	Local requiredFiles:TList=findRequiredFiles(requiredSymbols,symbols)
	Local modules:TList=getModuleNames(requiredFiles)
	

	Print "'===Module List for "+StripDir(path)+"==="

	'Time to trim the modules list down a bit

	For Local modName:String=EachIn modules
		
		Local modFiles:TList
		Local incMods:TList
		
		incMods=New TList
		modFiles=New TList
		
		scanModuleForImports(modName,modFiles,incMods)
		
		For Local incModName:String=EachIn incMods
			modules.Remove(incModName)
		Next
		
	Next
	
	
	addAdditionalModules(modules)
	
	Local modCount

	If modules.IsEmpty()
		If (isFirstFile)
			Print "Framework brl.blitz"
		Else
			Print "'This source file does not require any modules."
		EndIf
	EndIf
	
	For Local modName:String=EachIn modules
		If (modCount=0) And (isFirstFile)
			Print "FrameWork "+modName
		Else	
			If Left(modName,1)="'"
				Print modName
			Else
				Print "Import "+modName
			EndIf
		EndIf
	
		modCount :+ 1
	Next
	'EndRem
	
	isFirstFile=False

	Print Null
Next


Print "Search Completed - Took " + (scanStartTime-startTime) + " milliseconds to load symbols"..
	 +" and " + (MilliSecs()-scanStartTime) + " milliseconds to scan the source code and "..
	 +"remove redundant modules."

Type Symbol
	
	Const SYM_FUNCTION=1
	Const SYM_TYPE=2
	Const SYM_METHOD=3
	Const SYM_GLOBAL=4
	Const SYM_CONST=5
	
	Field name:String
	Field typeName:String
	Field kind:Int
	Field sourceFile:String
	Field sourceLine:Int
	
	Method Compare(other:Object)
	
		Local otherSymbol:Symbol=Symbol(other)
	
		If (name < otherSymbol.name)
			Return -1
		ElseIf (name > otherSymbol.name)
			Return 1
		Else
			Return 0
		End If
		
	End Method
End Type

'Returns the full path to the main source file for a given module, eg.
'moduleSourceFile("brl.max2d") will return "<BMAX Path>/mod/brl.mod/max2d.mod/max2d.bmx"
Function moduleSourceFile:String(modName:String)
	
	Return RealPath(modSourceFolder+"/"+modName.Replace(".",".mod/")+..
		".mod/"+ExtractExt(modName)+".bmx")
	
End Function

'Scans the specified module or source file and adds any files that module 
'depends on (directly or indirectly) to the files list, and names of modules
'which it depends on to the incModNames list.
Function scanModuleForImports(modName:String,files:TList,incModNames:TList)
	
	Local path:String
	
	If (modName.Find("/") < 0) And (modName.Find("") < 0)
		path=moduleSourceFile(modName)
	Else
		path=modName
	End If
	
	'Print path
	
	Local file:TStream=ReadFile(path)
	If Not file Return
	
	Local oldDir:String=CurrentDir()
	
	ChangeDir ExtractDir(path)
	
	
	While Not Eof(file)
		Local line:String=ReadLine(file).ToLower().Trim()
		
		Local firstWord:String=extractWord(line,0)
		
		If (firstWord="import") Or (firstWord="include")
			
			Local filePath:String=extractStringContents(line,0)
			
			If (filePath)
				If (FileType(filePath)=FILETYPE_FILE) And (ExtractExt(filePath)="bmx")
					If OnceOnlyAdd(files,RealPath(filePath))
						scanModuleForImports(RealPath(filePath),files,incModNames)
					EndIf
				End If
			Else
				Local importedMod:String=line[line.Find(" ")+1..].Trim()
				
				filePath=moduleSourceFile(importedMod)
				
				If OnceOnlyAdd(files,RealPath(filePath))
					scanModuleForImports(importedMod,files,incModNames)
					
					incModNames.AddLast(importedMod)
					'Print importedMod + " ("+StripDir(path)+")"
				EndIf
				
				
				
				
			End If
		End If
	End While

	CloseStream file
	
	ChangeDir oldDir
End Function

'Scans a given source file and adds a list of the source files it depends on to a TList
'object.  scanForImports works recursively.
Function scanForImports(path:String,list:TList)
	
	Local file:TStream=ReadFile(path)
	
	Local oldDir:String=CurrentDir()
	ChangeDir ExtractDir(path)
	
	While Not Eof(file)
		Local line:String=ReadLine(file).ToLower().Trim()
		
		Select extractWord(line,0)
			Case "import"
				Local fileName:String=extractStringContents(line,0)
				If (FileType(fileName)=FILETYPE_FILE) And (ExtractExt(fileName)="bmx") 
					If OnceOnlyAdd(list,RealPath(fileName))	
						scanForImports(list.Last().ToString(),list)
					EndIf
				EndIf
					
			Case "include"
				Local fileName:String=extractStringContents(line,0)
				
				If (FileType(fileName)=FILETYPE_FILE) And (ExtractExt(fileName)="bmx") 
					If OnceOnlyAdd(list,RealPath(fileName))
						scanForImports(list.Last().ToString(),list)
					EndIf
				EndIf
				
		End Select
		
	End While 
	
	ChangeDir oldDir
	
	
End Function

'Given a line of text with a string in, extractStringContents retrieves the text inside
'the quotes.  eg.  {Include "myfile.bmx"} will return {myfile.bmx} 
Function extractStringContents:String(line:String,startPos)

	Local strStart=-1
	
	For Local i=startPos Until line.length
		
		If (line[i]=Asc("~q"))
			If (strStart >= 0) Return line[strStart..i]
			strStart=i+1
		EndIf
			
	Next
	
	Return Null
	
EndFunction

'Looks at the list of modules and adds to the list any additional modules
'which it thinks may be needed.
Function addAdditionalModules(modList:TList)
	
	For Local modName:String=EachIn modList
	
		Select modName
			Case "brl.max2d"
				OnceOnlyAdd(modList,MOD_GL)
				OnceOnlyAdd(modList,MOD_PNG)
				OnceOnlyAdd(modList,MOD_BMP)
				OnceOnlyAdd(modList,MOD_JPG)
				OnceOnlyAdd(modList,MOD_TGA)
				OnceOnlyAdd(modList,MOD_FREETYPE)
			Case "brl.pixmap"
				OnceOnlyAdd(modList,MOD_PNG)
				OnceOnlyAdd(modList,MOD_BMP)
				OnceOnlyAdd(modList,MOD_JPG)
				OnceOnlyAdd(modList,MOD_TGA)
			Case "brl.audio"
				OnceOnlyAdd(modList,MOD_FREEAUDIO)
				OnceOnlyAdd(modList,MOD_OGG)
				OnceOnlyAdd(modList,MOD_WAV)
		End Select
	Next
EndFunction

'Checks a list to see if it contains the specified item.  If not it adds the item
'and returns TRUE, otherwise it just returns FALSE
Function OnceOnlyAdd(list:TList,item:Object)
	If (Not ListContains(list,item))
		list.AddLast(item)
		Return True
	Else
		Return False
	EndIf
EndFunction

'Checks the config file to get the path to the module sources.  If the config file is not
'found it prompts the user for the path and saves it in the config file.
Function getModSourceFolder:String()
	
	Local file:TStream=ReadFile("modscanner.cfg")
	Local modSourcePath:String
	If (file) And (Not Eof(file))
		modSourcePath=ReadLine(file)
		
		If (FileType(modSourcePath)<>FILETYPE_DIR) modSourcePath=Null
	End If
	If file CloseStream file
	
	If (Not modSourcePath)
		Notify "Please select your BlitzMAX module path.  This is the 'mod' folder inside " + ..
				"the directory where you installed BlitzMAX (eg. C:\BlitzMAX\mod)"
		
		'TODO - Replace with RequestDir
		modSourcePath=Input("Enter BlitzMAX Module Path > ")
		
		If FileType(modSourcePath)=FILETYPE_DIR
			file=WriteFile("modscanner.cfg")
			WriteLine file,modSourcePath
			CloseStream file
		
			Notify "Thank-you.  I promise I'll remember next time!"	
		Else
			End
		EndIf
	EndIf
	
	Return modSourcePath
			
End Function

'Takes a list of source files and returns a list of the modules which those files
'belong to.  Once modscanner has decided which source files are needed, getModuleNames
'produces the list of module names.
Function getModuleNames:TList(srcFiles:TList)
	Local result:TList=New TList
	
	For Local file:String=EachIn srcFiles
		Local folderPath:String=ExtractDir(RealPath(file)).ToLower()
		
		Local modPathStart=folderPath.find("mod/")
		
		If (modPathStart > -1)
			folderPath=folderPath[modPathStart..]
			Local pos=0
			Local modName:String
			
			pos=folderPath.Find("/")
			modName=Null
			
			While (pos>-1)
				Local modNameEnd=folderPath.Find(".",pos)
				
				If (modNameEnd>-1)
					If (modName)
						modName = modName+"."
					EndIf
					
					modName=modName+folderPath[pos+1..modNameEnd]
				End If
				
				pos = folderPath.find("/",pos+1)
			Wend
			
			'Note:  The brl.blitz module is automatically included, it doesn't need
			'to be added to the Imports list.
			If (Not ListContains(result,modName)) And (modName <> "brl.blitz")
			
				result.AddLast(modName)
			End If
		End If
	Next
	
	Return result
End Function

'Takes the list of functions and types required by a source file, and searches for them
'in the symbol tree which contains all of the funcs and types defined in the module sources
'
'findRequiredFiles returns a list of the source files which collectively contain the required
'functions and types.
Function findRequiredFiles:TList(requiredSymbols:Map,symbols:Map)
	Local result:TList=New TList
	
	For Local f:String=EachIn requiredSymbols
		Local k:Symbol=Symbol(symbols.findByKey(f))
		
		If (k)
			If (Not ListContains(result,k.sourceFile)) result.addLast(k.sourceFile)
		EndIf
	Next

	Return result
End Function

'Searches through the text of the specified source file and produces
'a list of the functions which are required to compile it.
Function findRequiredSymbols:Map(srcFile:String)
	
	Local file:TStream=ReadFile(srcFile)
	Local requires:Map=New Map
	
	Const basicTypes:String=".int.string.array.object.byte.short.long.float.double."
	Local typeName:String=Null
	
	While Not Eof(file)
		Local line:String=ReadLine(file).ToLower().Trim()
		If line[0]=Asc("'") Continue
		
		'Search For Needed Functions
		'==========================================================
		Local firstWord:String=extractWord(line,0)
		
		If (Not ListContains(keywordsList,firstWord))
			
			Local nextChr=getNextChr(line,Len(firstWord))
			
			If (nextChr <> Asc(":")) And (nextChr <> Asc("="))
				requires.insertOnce(firstWord,firstWord)
			End If
			
		End If
		
		
		For Local i=firstWord.Length Until line.length
			If (line[i]=Asc("(")) Or (line[i]=Asc("$"))
				Local name:String=extractWordRev(line,i-1)
				
				'Print "Req - " + name
				
				If (i-Len(name)) > 0
					
					If line[i-Len(name)-1]=Asc(".")
						Local typeName:String=extractWordRev(line,i-Len(name)-2)
						
						If (typeName.length > 0)
							name=typeName+"."+name
						EndIf
						
					End If
				End If
				
				If (Not ListContains(keywordsList,name))
					requires.insertOnce(name,name)
				End If
			EndIf
		Next
		
		'Search for Needed Types
		'===================================================
		If lineStartsWith(line,"type")
			
			Local extPos=line.Find(" extends ")
			
			If extPos > -1
	
				typeName=extractWord(line,extPos+Len(" extends "))
				
				If (typeName.length > 0)
					
						requires.insertOnce(typeName,typeName)
					'EndIf 
				End If
			End If
		End If
		
		For Local i=0 Until line.length
			If line[i]=Asc(":")
			
				typeName=extractWord(line,i+1)
				
				i:+typeName.length
				
				If (typeName.length > 0) And (basicTypes.find("."+typeName+".")=-1)
					'If (Not ListContains(requires,typeName))
						requires.insertOnce(typeName,typeName)
					'End If
				EndIf
			End If
		Next		
		
	End While
	
	CloseStream file
	
	Return requires
End Function

'Given a string with spaces in, it returns the first non-space character after the given
'starting position.
Function getNextChr(line:String,pos)
	For Local i=pos Until line.length
		If line[i] <> Asc(" ")
			Return line[i]
		End If
	Next
End Function

'Scans a folder recursively and adds any files whoose extensions match the filter array
'to a list.
Function addFolderContentsToList(folder:String,list:TList,filter:String[]=Null,recurse=True)
	
	Local dirHandle=ReadDir(folder)
	
	If (Not dirHandle) RuntimeError "Folder ~q"+folder+"~q does not exist."
	
	Local file:String
	Local shortFile:String
	
	Repeat 
		shortFile=NextFile(dirHandle)
		file=folder+"/"+shortFile
		
		If (shortFile <> ".") And (shortFile <> "..") And (shortFile <> "")
		
			
			Select FileType(file)
				Case FILETYPE_FILE
					
					If filter <> Null
						Local filterMatch=False
						
						For Local i:String=EachIn filter
							If ExtractExt(file)=i
								filterMatch=True
							End If
						Next
							
						If filterMatch list.AddLast(file)
					Else
						list.AddLast(file)
					End If
					
				Case FILETYPE_DIR
					'Print "Dir Encountered"
					If recurse
					'	Print "Recursing Into Dir"
						addFolderContentsToList(file,list,filter)
					End If
			End Select
		End If
		
	Until shortFile=""
	
	CloseDir dirHandle
End Function

'Extracts the name of the symbol from a string like "Function myFunc" or "Type myType",
'it only looks at the second word and assumes that the input string has already been trimmed
Function extractIdentName:String(line:String)
	
	Local nameStart=line.Find(" ")+1
	
	Local nameEnd=0
	Local pos=nameStart
	
	Repeat
		If Not isAlphaNum(line[pos]) nameEnd=pos;Exit
		
		pos :+ 1
		
		If pos=line.length nameEnd=line.length
	Until nameEnd
		
	Return line[nameStart..nameEnd]
	
End Function

'Extracts the alphanumeric word starting at a given position in a given string.
'Eg.  Given the string "helloWorld(123)" and position 0 it will return "helloWorld"
Function extractWord:String(line:String,startPos)

	Local nameEnd=0
	Local pos=startPos
	
	Repeat
		If Not isAlphaNum(line[pos]) nameEnd=pos;Exit
		
		pos :+ 1
		
		If pos=line.length nameEnd=line.length
	Until nameEnd
	
	Return line[startPos..nameEnd]

End Function

'Similar to the extractWord function, but the position argument endPos is the end of the word,
'rather than the start.
Function extractWordRev:String(line:String,endPos)

	Local nameStart=0
	Local pos=endPos
	
	Repeat
		If Not isAlphaNum(line[pos]) nameStart=pos+1;Exit
		
		pos :- 1
		
		If pos=0 Exit
	Forever
	
	Return line[nameStart..endPos+1]
End Function

'Returns true if the specified ASCII character code represents a letter or number
Function isAlphaNum(char)
	
	If ((char >= NUM_START) And (char <= NUM_END)) Return True
	If ((char >= UPPER_START) And (char <= UPPER_END)) Return True
	If ((char >= LOWER_START) And (char <= LOWER_END)) Return True
	If ((char = UNDERSCORE)) Return True
	
	Return False 	
End Function

'Looks at a line of BlitzMAX code and returns a number to indicate the kind of statement found.
'ie.  Whether it is a type, function, method, global or constant declaration.
Function identKind(line:String)
	If (Left(line,1)="'") Or (Left(line,3)="rem")
		Return 0
	End If
	
	If lineStartsWith(line,"type")
		Return 1
	EndIf
	
	If lineStartsWith(line,"end type")
		Return 2
	EndIf
	
	If lineStartsWith(line,"function")
		Return 3
	EndIf
	
	If lineStartsWith(line,"end function")
		Return 4
	EndIf
	
	If lineStartsWith(line,"method")
		Return 5
	EndIf
	
	If lineStartsWith(line,"end method")
		Return 6
	EndIf
	
	If lineStartsWith(line,"global")
		Return 7
	End If
	
	If lineStartsWith(line,"const")
		Return 8
	End If
	
End Function

'Returns True if the first characters in the string <line> are <test>
Function lineStartsWith(line:String,test:String)
	If Left(line,Len(test))=test 
		Return True
	Else
		Return False
	End If
End Function

'Scans a list of source files and produces a tree (or 'Map') containing data about all of the symbols
'(functions, types, globals, constants etc.) which are found.
'
'modscanner creates a cache of the symbols found, so this only needs to be done
'for the module sources when a change is detected
Function extractSymbols:Map(modFiles:TList)

	Print "Building Symbol List..."
	
Local symbols:Map=New Map

For Local i:String = EachIn modFiles
	
	Local source:TStream=OpenFile(i)
	Local lineCount
	Local inComment
	Local currentType:String=Null
	
	inComment=0
	lineCount=0
		
	While Not Eof(source)
		Local line:String=ReadLine(source).ToLower().Trim()
		lineCount :+ 1
		
		If line[0]=Asc("'") Continue
		
		If Left(line,3)="rem" inComment=True
		'This just deals with a bug in early IDEs
		If lineStartsWith(line,"end r"+"em") inComment=False
		If lineStartsWith(line,"endr"+"em") inComment=False
		
		Local kind=identKind(line)
		
		If inComment kind=-1
		
		If kind=3	
				Local newSym:Symbol=New Symbol
			
				If (currentType)
					newSym.name=currentType+"."+extractIdentName(line)
				Else
					newSym.name=extractIdentName(line)
				End If
				
				newSym.typeName=currentType
				newSym.kind=newSym.SYM_FUNCTION
				newSym.sourceFile=i
				newSym.sourceLine=lineCount
				
				symbols.insert(newSym.name,newSym)
		EndIf
		
		If kind=1
				currentType=extractIdentName(line)
				
				Local newSym:Symbol=New Symbol
			
				newSym.name=currentType
				newSym.typeName=Null
				newSym.kind=newSym.SYM_TYPE
				newSym.sourceFile=i
				newSym.sourceLine=lineCount
						
				symbols.insert(newSym.name,newSym)
		EndIf
		
		If kind=2
				currentType=Null
		EndIf
		
		If kind=5			
				Local newSym:Symbol=New Symbol
				
				newSym.name=currentType+"."+extractIdentName(line)
				newSym.typeName=currentType
				newSym.kind=newSym.SYM_METHOD
				newSym.sourceFile=i
				newSym.sourceLine=lineCount
				
				symbols.insert(newSym.name,newSym)
	
		End If
		
		If kind=7
				Local newSym:Symbol=New Symbol
				newSym.name=extractIdentName(line)
				newSym.typeName=currenttype
				newSym.kind=newSym.SYM_GLOBAL
				newSym.sourceFile=i
				newSym.sourceLine=lineCount
				
				symbols.insert(newSym.name,newSym)
		End If
		
		If kind=8
				Local newSym:Symbol=New Symbol
				newSym.name=extractIdentName(line)
				newSym.typeName=currentType
				newSym.kind=newSym.SYM_CONST
				newSym.sourceFile=i
				newSym.sourceLine=lineCount
				
				symbols.insert(newSym.name,newSym)
		End If
		
		FlushMem
		
	End While
	
	CloseFile(source)
Next

Return symbols

End Function

'Dumps a tree of symbol information to the cache file, for faster loading on future runs.
Function saveSymbols(sym:Map)
	
	Print "Saving Symbol Cache..."
	
	Local symList:TList=sym.enumValuesUnsorted()
	Local symSources:Map=New Map
	
	Local cache:TStream=WriteFile("symbols.cache")

	For Local sym:Symbol=EachIn symList
		Local typeNameInfo:String=sym.typeName
		If typeNameInfo.length=0 typeNameInfo="null"
		
		WriteLine cache,sym.name+"|"+typeNameInfo+"|"+sym.kind+"|"+sym.sourceFile+"|"..
		+sym.sourceLine
	
		
			If (Not symSources.findByKey(sym.SourceFile))
				symSources.insert(sym.SourceFile,sym.sourceFile)
			EndIf
		
		
		FlushMem
	Next
	
	CloseFile cache
	
	Local fileList:TStream=WriteFile("symbols.files.cache")
	
	Local symFiles:TList=symSources.enumValues()
	For Local symFile:String = EachIn symFiles
		WriteLine fileList,symFile
		WriteLine fileList,FileTime(symFile)
	Next
	
	CloseFile fileList
	
End Function

'loadSymbols creates a tree of the symbols found in the module sources folder.
'It first checks the saved cache, and loads data from it if it is up-to-date.  If source
'files have changed since the cache was created, it rebuilds the cache from scratch.
Function loadSymbols:Map(modFiles:TList)
	
	
	Local symList:Map
	
	'Try
		If VerifyCache()
			FlushMem
		
			symList=New Map
		
			Local cache:TStream=ReadFile("symbols.cache")
		
			Print "Loading Symbol Cache..."
		
			While (Not Eof(cache))
			
				Local line:String=ReadLine(cache)
			
				Local newSym:Symbol=New Symbol
			
				Local elements:String[]=split(line,"|")
			
				newSym.name=elements[0]
			
				If (elements[1]<>"null")
					newSym.typeName=elements[1]
				End If
			
				newSym.kind=elements[2].ToInt()
			
				newSym.sourceFile=elements[3]
				newSym.sourceLine=elements[4].ToInt()
			
				symList.insert(newSym.name,newSym)
		
				FlushMem
			End While
		
		CloseFile cache
	Else
		symList=extractSymbols(modFiles)
		saveSymbols(symList)
	EndIf
	
	'Catch o:Object
	Rem
		Print "Oh dear - Something went wrong whilst loading the cache, let's try a rebuild..."
		
		Try
			symList=extractSymbols(modFiles)
			saveSymbols(symList)
			Print "Yup, that fixed it."
		Catch o:Object
			Print "Nope, that didn't work.  Oh well, worth a try."
			Print "Goodbye Cruel World!"
			Print "Aghhhhhh!...."
			Print "(The Program died a violent death)"
			End
		End Try
	'End Try
	EndRem
	
	Return symList
End Function

'verifyCache returns TRUE if the symbol cache file is found and is up to date (it checks
'by comparing the file modification times stored in symbols.files.cache against the current
'modification times of those files).  
'If the cache is not found or is out of date verifyCache returns FALSE.
'
'verifyCache doesn't check the symbols.cache file for corruption, although it really ought to.
Function verifyCache()
	Print "Verifying Symbol Cache..."
	
	If FileType("symbols.cache")<>FILETYPE_FILE Return False
	
	Local cache:TStream=ReadFile("symbols.files.cache")
	
	If cache
		While Not Eof(cache)
			Local srcFile:String=ReadLine(cache)
			Local time=ReadLine(cache).ToInt()
			
			If FileTime(srcFile) <> time
				CloseStream cache
				Return False
			End If
		End While			
	Else
		Print "Cache not found..."
		Return False
	End If
	
	CloseStream cache
	Return True
End Function

'A good ol' string split function.  Takes a string which is delimited by a specified character
'or substring, and returns an array of the substrings found.
'eg.  split("A-B-C","-") returns ["A","B","C"]
Function split:String[](str:String,delimiter:String)
	
	Local result:String[]
	Local temp:String
	
	'Verify input
	If delimiter.length < 1 Then Return Null
	
	Local pos
	Local searchStart
	Local elements
	
	'Split the string
	Repeat
		'Locate the next occurance of the delimiter within the string
		pos=str.Find(delimiter,searchStart)
	
		'If the delimiter was found, set the temporary string to the part of the source string
		'between searchStart and pos, otherwise set it to the rest of the source string	
		
		If pos > -1
			temp=str[searchStart..pos]
		Else
			temp=str[searchStart..]
		EndIf
		
		'Increase the size of the result array by one as long as the new element has a length of one or more
		If temp.length > 0
			elements :+ 1
		
			result = result[..elements]
		
			result[elements-1]=temp
		EndIf		
	
		'Move the starting to point for the next search to just after the delimiter
		searchStart = pos+delimiter.length
		
		'Return once a search for the delimiter has failed (ie. we have completed the split process)
	Until pos < 0
	
	Return result
End Function

map.bmx

'Title:   map.bmx
'Author:  Robert Knight
'
'Simplistic implementation of a binary tree data structure, or 'Map'.
'Binary Trees are a way of storing items of data using a key (which is unique to each item)
'and a corresponding value.  Binary Trees (when set up correctly) can be searched very quickly.
'

Import BRL.LinkedList
Import BRL.StandardIO 

'A map is made up of a series of MapNode objects.  Each MapNode contains a key, which can 
'be searched for, a value which is useful data of some sort, and references to the MapNode's
'left and right children (either or both of which may be null).
'The left child's key will always be less than the node's own key, and the right child's key
'will always be greater than the node's own key, whether the key is a number, string or something
'else.
Type MapNode
	Field _value:Object
	Field _key:Object
	
	Field _left:MapNode
	Field _right:MapNode
	
	Field _pushed
End Type

Type MapEnumerator
	Field _map:Map
	Field _stack:TList
	Field _current:MapNode
	
	Method traverseLeftNode(node:MapNode)
		While (node <> Null)
			_stack.AddLast(node)
			node=node._left
		End While
	End Method
	
	Method init()
		_current=_map._root
		_stack=New TList
		traverseLeftNode(_current)
	End Method
	
	Method HasNext()
		
		If (Not _stack) Return False
		Return (Not _stack.IsEmpty())
		
	End Method
	
	Method NextObject:Object()
		
		_current=MapNode(_stack.RemoveLast())
		
		Local result:Object=_current._value
		
		_current=_current._right
		
		traverseLeftNode(_current)
		
		Return result
	End Method
End Type

'Class for storing data in an organised way for fast searching.
Type Map
	Field _root:MapNode
	
	'Produces an sorted list of all the values stored in the map
	Method enumValues:TList()
		Local list:TList=New TList
		
		_findNext(_root,list)
		
		Return list
	End Method
	
	
	'Produces an unsorted list of all the values stored in the map.  Although sorted lists
	'are useful for display purposes, if we need to insert these values back into another map
	'later, pushing the values in a sorted order will cause the resulting Map to be extremely
	'inefficient.  
	'
	'Sidenote:
	'A perfectly efficient map would only need to check a maximum of (log(# of items)/log 2) 
	'MapNodes to find any item in the map.  The worst case scenario is when items are added
	'in sorted order, and in that case a Map is no better than an ordinary linked-list.
	Method enumValuesUnsorted:TList()
		Local list:TList=New TList
		
		_findNextUnsorted(_root,list)
		
		Return list
	End Method
	
	Method _findNext(node:MapNode,list:TList)
		If (node._left)
			_findNext(node._left,list)
		EndIf
		
		list.AddLast(node._value)
		
		If (node._right)
			_findNext(node._right,list)
		End If
	End Method
	
	Method _findNextUnsorted(node:MapNode,list:TList)
		list.AddLast(node._value)
		
		If (node._left)
			_findNextUnsorted(node._left,list)
		EndIf
		
		If (node._right)
			_findNextUnsorted(node._right,list)
		EndIf
		
	End Method

	
	Method insertOnce(key:Object,value:Object)
		If (Not findByKey(key))
			insert(key,value)
		End If
	End Method
	
	'Given a value and a unique key associated with it, the insert method creates a new MapNode
	'and tucks the data away in the right place in the tree.
	Method insert(key:Object,value:Object)
		
		Local newNode:MapNode=New MapNode
		newNode._key=key
		newNode._value=value
		
		If (Not _root)
			_root=newNode
		Else
			Local current:MapNode=_root
			
			'Local ct
			
			Repeat
				'ct :+ 1
				If key.Compare(current._key) < 0
					'Print "kc left"
					If current._left
						current=current._left
						Continue
					Else
						current._left=newNode
						'Print "Left - " + ct
						Return
					End If
				Else
					If current._right
						current=current._right
						Continue
					Else
						current._right=newNode
						'Print "Right - " + ct
						Return
					End If
				End If
				
				
			Forever
			
		
		End If	
		
	End Method
	
	Method ObjectEnumerator:MapEnumerator()
		Local enum:MapEnumerator=New MapEnumerator
		
		enum._map=Self
		enum.init()
		
		Return enum
	End Method
	
	'Finds the value associated with a given key in the map.
	'The <MapNode> parameter is the optional starting node to begin searching from.
	'It defaults to the map's root node if left as Null (ie. the whole tree will be searched)
	Method findByKey:Object(key:Object, obj:MapNode=Null)
		
		If Not _root Return Null
		
		If (Not obj) obj=_root
		
		
		If key.Compare(obj._key)<0
			If Not obj._left Return Null
			
			Return findByKey(key,obj._left)
		Else
			If key.Compare(obj._key)>0
				If Not obj._right Return Null
				
				Return findByKey(key,obj._right)
			Else
				
				Return obj._value
			End If
		End If
	End Method
	 
End Type