[Enhancement] Find reference

[my-vegetable-has-exploded]

Find References provides all references to an identifier under the current workspace.

Goto Defintion requires resolving the location of the symbol definition of an identifier with a given text location.

lsp Protocol: The lsp protocol is use to exchang message between development tools and language server processes. Tools such as VS Code use the JSON-RPC language protocol to communicate with the language server.

Related user operations include create files, change files, delete files, rename files, find references, and goto definition.

The ide side uses json-rpc to send Notification or Requests which contains the parameters based on the user's actions to the lsp client in kclvm-go . Part of the requests need to be sent to the language server in kclvm for further processing via rpc requests by kclvm-go.

To speed up the word search process, this issue build index on identifiers. Thus, WorkspaceWordMap and FileWordsMap are built.

Position includes the string type fileName and its offset in the file offest (which can also be represented by line and column).

FileWordsMap indexes the identifiers in certain file, and for each name , maintains a vector to record its all occurrence position in the file.

Method Description:

• void clear()

  • used to clear the FileWordsMap when certain file is deleted by user, etc.

    for name, vec in range(wordMap){
    	vec.clear();
    }	
    

• void insert(name, pos)

  • Add the identifier's name text and it's location pos into the file's identifier index

wordMap.get_mut(name).append(pos);

• void build(fileName,text)
  • build index for a file based on its text

words=text_to_words(text);
for word in words{
	self.insert(word.name, word.pos);
}

• vec get(name)
  • for a name, return its all occurrence position in the file.

return wordMap.get(name)

WorkspaceWordMap build indexes for all the files under the current workspace, and maintain them in a hashMap.

• void changeFile(fileName, text)
  • user edit a file, and send the new file text . To response to the user's changes, the previous file index needs to be modified.

fileMap.get_mut(fileName).build();

• void createFile(fileName)
  • user creates a new file and needs to maintain a new file index in WorkspaceMap.

fileMap.insert(filename, FileWordMap::new());

• void renameFile(oldFileName, newFileName)
  • user rename a file name , the workspace map needs to change the key in the file index from the old file name to the new file name.

fileMap.remove(oldFilaName)
fileMap.insert(filename, FileWordMap::new(newFileName).build());

• void deleteFile(fileName)
  • when user delete a file, the workspace map needs to remove the index of the file from the workspace index.

fileMap.remove(oldFileName)

• void build(path)
  • building an index on the current path (current workspace) will iterate through all kcl files in the current workspace, creating a file index for each kcl file.

for file in os.path(path){
	if file.name.suffix==".k"{ 
		v=FileWordMap::new();
		v.build(file.name, file.text);
		fileMap.insert(file.name,v);
	}
}

• Vector<Position> get(name)
  • Given an identifier name, find all occurrences of identifiers with the same name from the current workspace. By traversing the file indexes in each file, this method returns a merged vector of position.

results=vec::new();
for filename, fileWordMap in range(fileMap){
	results.extend(fileWordMap.get(name));
}
return results;

•The main process of Find References for the symbol S is as follows.

1. create a symbol table/word table for all kcl files in the current workspace

2. reuse the GotoDefintion to get the Definition S' of the symbol S

3. get the all symbol R with same name and their positions based on the index

4. Iterate through the matched symbols R obtained in step 3, and obtain the Definition R' of the symbol R using the GotoDefintion logic and the syntax and semantic analysis results of the files in which they are located. return all symbols R whose defintion R' equals to S'.

对于find refs的一些case，首先是可能definition的name和references的name不一致的情况， 如类中使用super、self来表示引用基类时，需要将self也加入搜索范围，以及某些语言使用鸭子类型在实现interface中没有显式地声明。但是kcl中不支持self、super，对于schema而言，mixin和protocol也是需要显式声明的，感觉可能不存在这种问题。 多次使用import as或其它类似as功能的语句等，是否需要考虑传递性呢？ 还有s就是有一些definition不完全一致的case（这方面我不太理解）。

further step

By maintaining a use map recording identifiers and their definition object, the langserver can get reference without searching the whole workspace. The use map need to record normal variable, package, function ,schema and schema's fields and so on. But how to maintain indexes when users modify files requires further consideration.

[He1pa]

In KCL, we have build a structure similar to the symbol table and we call it scope. You can find it in kclvm/sema/src/resolver/scope.rs. It records most of the information you need, such as position, file, etc. Maybe you can do your work base on this structure.

By the way, I don't know why you need methods renameFile, createFile and deleteFile

[my-vegetable-has-exploded]

In KCL, we have build a structure similar to the symbol table and we call it scope. You can find it in kclvm/sema/src/resolver/scope.rs. It records most of the information you need, such as position, file, etc. Maybe you can do your work base on this structure.

In my opinion, the scope only records definitions but don't contain information of references, so i think there is still a need to introduce the map.

By the way, I don't know why you need methods renameFile, createFile and deleteFile

Because this map won't rebuild completely for every time when user invokes find_refs. I think it is necessary to keep pace with user's changes so that the map won't return Invalidate results.