Implement `map<any>` - Githubissues

ballerina-platform / nballerina

Ballerina compiler that generates native executables.

https://ballerina.io/

Apache License 2.0

138 stars 46 forks source link

Implement `map<any>` #170

Closed jclark closed 3 years ago

jclark commented 3 years ago

This introduces a new type descriptor map<any>.

New type descriptor: map<any>
New expressions
- mapping constructors { "xyz": E } - allowed in same syntactic contexts as list constructors
Langlib
- map:length

Existing syntax extended:

===, !==
io:println handles maps
E[k]
M[k] = E
<map<any>>E

This depends on #130.

Implementation steps:

[x] Design AST for mapping constructor and parse into it
[x] Add MappingConstruct BIR instruction and generate from the AST
[x] Design runtime for constructing a map and extend io:println to print it
[x] Generate LL for MappingConstruct BIR
[x] Add map<any> type descriptor
[x] Test and fix up equality operator for map<any>
[x] Implement map:length langlib function
[x] Implement casts to map<any>
[x] Implement runtime string hashing function
[x] Implement runtime for accessing map members via hashing
[x] Implement E[k] and MappingGet BIR insn
[x] Implement v[k] = n with MappingSet BIR insn
[x] More tests

jclark commented 3 years ago

A good implementation strategy would be Python's "compact dict" data structure. https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html

See also: https://blog.toit.io/hash-maps-that-dont-hate-you-1a96150b492a

This is a good balanced overview https://bigdata.uni-saarland.de/publications/p249-richter.pdf