hashes

11 files changed, 404 insertions, 1 deletions

diff --git a/README.md b/README.md
index 7d79c8f..4128a43 100644
--- a/README.md
+++ b/README.md
@@ -27,7 +27,7 @@ Mana is a toy programming language written in Go. It is a dynamically typed, int
 | `BuiltInFunctions`          | ✔️     | Built-in Functions are functions that are built into the language       | `len("Hello, World!")`     | ✔️    |
 | `ArrayLiteralExpression`    | ✔️     | Array Literal Expressions are used to represent array values            | `[1, 2, 3]`                | ✔️    |
 | `IndexExpression`           | ✔️     | Index Expressions are used to index into arrays                         | `myArray[0]`               | ✔️    |
-| `HashLiteralExpression`     | NYI    | Hash Literal Expressions are used to represent hash values              | `{"key": "value"}`         | NYI   |
+| `HashLiteralExpression`     | ✔️     | Hash Literal Expressions are used to represent hash values              | `{"key": "value"}`         | ✔️    |
 
 \*_NYI = Not Yet Implemented_
 
@@ -178,6 +178,25 @@ let u = ["one", "two", 3][5 - 4]; // u = "two"
 let k = mixed[c - 67]; // k = true
 ```
 
+## Hashes
+
+Hashes in Mana are unordered collections of key-value pairs. Hashes are created using curly braces. Hashes can contain keys of `supported types` (**Boolean**, **Integers**, and **Strings** - Objects which implement the `Hashable` interface). Hashes can contain values of any type, including other hashes. Hashes are indexed using square brackets. The index is a key that represents the key of the element in the hash.
+
+```rust
+let person = {
+    "name": "Alice",
+    "age": 30,
+    "isStudent": false,
+    "address": {
+        "street": "123 Main St",
+        "city": "Anytown"
+    }
+};
+
+let name = person["name"]; // name = "Alice"
+let city = person["address"]["city"]; // city = "Anytown"
+```
+
 ## Building Advanced Functions
 
 **Map**
diff --git a/ast/ast.go b/ast/ast.go
index cc30808..eed1595 100644
--- a/ast/ast.go
+++ b/ast/ast.go
@@ -349,3 +349,25 @@ func (ie *IndexExpression) String() string {
 
 	return out.String()
 }
+
+type HashLiteral struct {
+	Token tokens.Token
+	Pairs map[Expression]Expression
+}
+
+func (hl *HashLiteral) expressionNode()      {}
+func (hl *HashLiteral) TokenLiteral() string { return hl.Token.Literal }
+func (hl *HashLiteral) String() string {
+	var out bytes.Buffer
+
+	pairs := []string{}
+	for key, value := range hl.Pairs {
+		pairs = append(pairs, key.String()+":"+value.String())
+	}
+
+	out.WriteString("{")
+	out.WriteString(strings.Join(pairs, ", "))
+	out.WriteString("}")
+
+	return out.String()
+}
diff --git a/evaluator/evaluator.go b/evaluator/evaluator.go
index 913138b..5e988cc 100644
--- a/evaluator/evaluator.go
+++ b/evaluator/evaluator.go
@@ -110,6 +110,9 @@ func Eval(node ast.Node, env *object.Environment) object.Object {
 	case *ast.StringLiteral:
 		return &object.String{Value: node.Value}
 
+	case *ast.HashLiteral:
+		return evalHashLiteral(node, env)
+
 	case *ast.ReturnStatement:
 		val := Eval(node.ReturnValue, env)
 		if isError(val) {
@@ -319,6 +322,8 @@ func evalIndexExpression(left, index object.Object) object.Object {
 	switch {
 	case left.Type() == object.ARRAY_OBJ && index.Type() == object.INTEGER_OBJ:
 		return evalArrayIndexExpression(left, index)
+	case left.Type() == object.HASH_OBJ:
+		return evalHashIndexExpression(left, index)
 	default:
 		return newError("index operator not supported: %s", left.Type())
 	}
@@ -348,6 +353,48 @@ func evalIdentifier(node *ast.Identifier, env *object.Environment) object.Object
 	return newError("identifier not found: " + node.Value)
 }
 
+func evalHashLiteral(node *ast.HashLiteral, env *object.Environment) object.Object {
+	pairs := make(map[object.HashKey]object.HashPair)
+
+	for keyNode, valueNode := range node.Pairs {
+		key := Eval(keyNode, env)
+		if isError(key) {
+			return key
+		}
+
+		hashKey, ok := key.(object.Hashable)
+		if !ok {
+			return newError("unusable as hash key: %s", key.Type())
+		}
+
+		value := Eval(valueNode, env)
+		if isError(value) {
+			return value
+		}
+
+		hashed := hashKey.HashKey()
+		pairs[hashed] = object.HashPair{Key: key, Value: value}
+	}
+
+	return &object.Hash{Pairs: pairs}
+}
+
+func evalHashIndexExpression(hash, index object.Object) object.Object {
+	hashObject := hash.(*object.Hash)
+
+	key, ok := index.(object.Hashable)
+	if !ok {
+		return newError("unusable as hash key: %s", index.Type())
+	}
+
+	pair, ok := hashObject.Pairs[key.HashKey()]
+	if !ok {
+		return NULL
+	}
+
+	return pair.Value
+}
+
 func isTruthy(obj object.Object) bool {
 	switch obj {
 	case NULL:
diff --git a/evaluator/evaluator_test.go b/evaluator/evaluator_test.go
index 3c72cda..f1d28d0 100644
--- a/evaluator/evaluator_test.go
+++ b/evaluator/evaluator_test.go
@@ -185,6 +185,10 @@ func TestErrorhandling(t *testing.T) {
 			`"Hello" - "World"`,
 			"unknown operator: STRING - STRING",
 		},
+		{
+			`{"name": "Monkey"}[fn(x) { x }];`,
+			"unusable as hash key: FUNCTION",
+		},
 	}
 
 	for _, tt := range tests {
@@ -456,3 +460,89 @@ func TestArrayIndexExpressions(t *testing.T) {
 		}
 	}
 }
+
+func TestHashLiterals(t *testing.T) {
+	input := `let two = "two";
+	{
+		"one": 10 - 9,
+		two: 1 + 1,
+		"thr" + "ee": 6 / 2,
+		4: 4,
+		true: 5,
+		false: 6
+	}`
+
+	evaluated := testEval(input)
+	result, ok := evaluated.(*object.Hash)
+	if !ok {
+		t.Fatalf("Eval didn't return Hash. got=%T (%+v)", evaluated, evaluated)
+	}
+
+	expected := map[object.HashKey]int64{
+		(&object.String{Value: "one"}).HashKey():   1,
+		(&object.String{Value: "two"}).HashKey():   2,
+		(&object.String{Value: "three"}).HashKey(): 3,
+		(&object.Integer{Value: 4}).HashKey():      4,
+		TRUE.HashKey():                             5,
+		FALSE.HashKey():                            6,
+	}
+
+	if len(result.Pairs) != len(expected) {
+		t.Fatalf("Hash has wrong num of pairs. got=%d", len(result.Pairs))
+	}
+
+	for expectedKey, expectedValue := range expected {
+		pair, ok := result.Pairs[expectedKey]
+		if !ok {
+			t.Errorf("no pair for given key in Pairs")
+		}
+
+		testIntegerObject(t, pair.Value, expectedValue)
+	}
+}
+
+func TestHashIndexExpressions(t *testing.T) {
+	tests := []struct {
+		input string
+		expected interface{}
+	}{
+		{
+			`{"foo": 5}["foo"]`,
+			5,
+		},
+		{
+			`{"foo": 5}["bar"]`,
+			nil,
+		},
+		{
+			`let key = "foo"; {"foo": 5}[key]`,
+			5,
+		},
+		{
+			`{}["foo"]`,
+			nil,
+		},
+		{
+			`{5: 5}[5]`,
+			5,
+		},
+		{
+			`{true: 5}[true]`,
+			5,
+		},
+		{
+			`{false: 5}[false]`,
+			5,
+		},
+	}
+
+	for _, tt := range tests {
+		evaluated := testEval(tt.input)
+		integer, ok := tt.expected.(int)
+		if ok {
+			testIntegerObject(t, evaluated, int64(integer))
+		} else {
+			testNullObject(t, evaluated)
+		}
+	}
+}
diff --git a/lexer/lexer.go b/lexer/lexer.go
index 73326b3..971d738 100644
--- a/lexer/lexer.go
+++ b/lexer/lexer.go
@@ -69,6 +69,8 @@ func (l *Lexer) NextToken() tokens.Token {
 		tok = newToken(tokens.LBRACKET, l.ch)
 	case ']':
 		tok = newToken(tokens.RBRACKET, l.ch)
+	case ':':
+		tok = newToken(tokens.COLON, l.ch)
 	case '"':
 		tok.Type = tokens.STRING
 		tok.Literal = l.readString()
diff --git a/lexer/lexer_test.go b/lexer/lexer_test.go
index bac1102..9d6fc52 100644
--- a/lexer/lexer_test.go
+++ b/lexer/lexer_test.go
@@ -30,6 +30,7 @@ func TestNextToken(t *testing.T) {
 		"foobar"
 		"foo bar"
 		[1, 2];
+		{"foo": "bar"}
 	`
 
 	var tests = []struct {
@@ -117,6 +118,11 @@ func TestNextToken(t *testing.T) {
 		{tokens.INT, "2"},
 		{tokens.RBRACKET, "]"},
 		{tokens.SEMICOLON, ";"},
+		{tokens.LBRACE, "{"},
+		{tokens.STRING, "foo"},
+		{tokens.COLON, ":"},
+		{tokens.STRING, "bar"},
+		{tokens.RBRACE, "}"},
 		{tokens.EOF, ""},
 	}
 
diff --git a/object/object.go b/object/object.go
index 9fe896e..22d0441 100644
--- a/object/object.go
+++ b/object/object.go
@@ -3,6 +3,7 @@ package object
 import (
 	"bytes"
 	"fmt"
+	"hash/fnv"
 	"mana/ast"
 	"strings"
 )
@@ -19,6 +20,7 @@ const (
 	ERROR_OBJ        = "ERROR"
 	BUILTIN_OBJ      = "BUILTIN"
 	ARRAY_OBJ        = "ARRAY"
+	HASH_OBJ         = "HASH"
 )
 
 type Object interface {
@@ -144,3 +146,61 @@ func (ao *Array) Inspect() string {
 
 	return out.String()
 }
+
+type HashKey struct {
+	Type  ObjectType
+	Value uint64
+}
+
+func (b *Boolean) HashKey() HashKey {
+	var value uint64
+
+	if b.Value {
+		value = 1
+	} else {
+		value = 0
+	}
+
+	return HashKey{Type: b.Type(), Value: value}
+}
+
+func (i *Integer) HashKey() HashKey {
+	return HashKey{Type: i.Type(), Value: uint64(i.Value)}
+}
+
+func (s *String) HashKey() HashKey {
+	h := fnv.New64a()
+	h.Write([]byte(s.Value))
+
+	return HashKey{Type: s.Type(), Value: h.Sum64()}
+}
+
+type HashPair struct {
+	Key   Object
+	Value Object
+}
+
+type Hash struct {
+	Pairs map[HashKey]HashPair
+}
+
+func (h *Hash) Type() ObjectType { return HASH_OBJ }
+
+func (h *Hash) Inspect() string {
+	var out bytes.Buffer
+
+	pairs := []string{}
+	for _, pair := range h.Pairs {
+		pairs = append(pairs, fmt.Sprintf("%s: %s", pair.Key.Inspect(), pair.Value.Inspect()))
+	}
+
+	out.WriteString("{")
+	out.WriteString(strings.Join(pairs, ", "))
+	out.WriteString("}")
+
+	return out.String()
+}
+
+type Hashable interface {
+	HashKey() HashKey
+}
diff --git a/object/object_test.go b/object/object_test.go
new file mode 100644
index 0000000..3d08c8b
--- /dev/null
+++ b/object/object_test.go
@@ -0,0 +1,22 @@
+package object
+
+import "testing"
+
+func TestStringhashKey(t *testing.T) {
+	hello1 := &String{Value: "Hello World"}
+	hello2 := &String{Value: "Hello World"}
+	diff1 := &String{Value: "My name is johnny"}
+	diff2 := &String{Value: "My name is johnny"}
+
+	if hello1.HashKey() != hello2.HashKey() {
+		t.Errorf("strings with same content have different hash keys")
+	}
+
+	if diff1.HashKey() != diff2.HashKey() {
+		t.Errorf("strings with same content have different hash keys")
+	}
+
+	if hello1.HashKey() == diff1.HashKey() {
+		t.Errorf("strings with different content have same hash keys")
+	}
+}
\ No newline at end of file
diff --git a/parser/parser.go b/parser/parser.go
index 4fa36b1..2de9e56 100644
--- a/parser/parser.go
+++ b/parser/parser.go
@@ -75,6 +75,7 @@ func New(l *lexer.Lexer) *Parser {
 	p.registerPrefix(tokens.LPAREN, p.parseGroupedExpression)
 	p.registerPrefix(tokens.STRING, p.parseStringLiteral)
 	p.registerPrefix(tokens.LBRACKET, p.parseArrayLiteral)
+	p.registerPrefix(tokens.LBRACE, p.parseHashLiteral)
 
 	// Initialize the infix parse functions.
 	p.infixParseFns = make(map[tokens.TokenType]infixParseFn)
@@ -494,6 +495,35 @@ func (p *Parser) parseIndexExpression(left ast.Expression) ast.Expression {
 	return exp
 }
 
+func (p *Parser) parseHashLiteral() ast.Expression {
+	hash := &ast.HashLiteral{Token: p.curToken}
+	hash.Pairs = make(map[ast.Expression]ast.Expression)
+
+	for !p.peekTokenIs(tokens.RBRACE) {
+		p.nextToken()
+		key := p.parseExpression(LOWEST)
+
+		if !p.expectPeek(tokens.COLON) {
+			return nil
+		}
+
+		p.nextToken()
+		value := p.parseExpression(LOWEST)
+
+		hash.Pairs[key] = value
+
+		if !p.peekTokenIs(tokens.RBRACE) && !p.expectPeek(tokens.COMMA) {
+			return nil
+		}
+	}
+
+	if !p.expectPeek(tokens.RBRACE) {
+		return nil
+	}
+
+	return hash
+}
+
 // curTokenIs returns true if the current token is of the given type.
 func (p *Parser) curTokenIs(t tokens.TokenType) bool {
 	return p.curToken.Type == t
diff --git a/parser/parser_test.go b/parser/parser_test.go
index 7b347f5..e38301a 100644
--- a/parser/parser_test.go
+++ b/parser/parser_test.go
@@ -859,3 +859,107 @@ func TestParsingIndexExpressions(t *testing.T) {
 		return
 	}
 }
+
+func TestParsingHashLiteralsStringKeys(t *testing.T) {
+	input := `{"one": 1, "two": 2, "three": 3}`
+
+	var l *lexer.Lexer = lexer.New(input)
+	var p *Parser = New(l)
+
+	var program *ast.Program = p.ParseProgram()
+	checkParserErrors(t, p)
+
+	stmt := program.Statements[0].(*ast.ExpressionStatement)
+	hash, ok := stmt.Expression.(*ast.HashLiteral)
+	if !ok {
+		t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
+	}
+
+	if len(hash.Pairs) != 3 {
+		t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
+	}
+
+	expected := map[string]int64{
+		"one":   1,
+		"two":   2,
+		"three": 3,
+	}
+
+	for key, value := range hash.Pairs {
+		literal, ok := key.(*ast.StringLiteral)
+		if !ok {
+			t.Errorf("key is not ast.StringLiteral. got=%T", key)
+		}
+
+		expectedValue := expected[literal.Value]
+		testIntegerLiteral(t, value, expectedValue)
+	}
+}
+
+func TestParsingEmptyHashLiteral(t *testing.T) {
+	input := `{}`
+
+	var l *lexer.Lexer = lexer.New(input)
+	var p *Parser = New(l)
+
+	var program *ast.Program = p.ParseProgram()
+	checkParserErrors(t, p)
+
+	stmt := program.Statements[0].(*ast.ExpressionStatement)
+	hash, ok := stmt.Expression.(*ast.HashLiteral)
+	if !ok {
+		t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
+	}
+
+	if len(hash.Pairs) != 0 {
+		t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
+	}
+}
+
+func TestParsingHashLiteralsWithExpressions(t *testing.T) {
+	input := `{"one": 0 + 1, "two": 10 - 8, "three": 15 / 5}`
+
+	var l *lexer.Lexer = lexer.New(input)
+	var p *Parser = New(l)
+
+	var program *ast.Program = p.ParseProgram()
+	checkParserErrors(t, p)
+
+	stmt := program.Statements[0].(*ast.ExpressionStatement)
+	hash, ok := stmt.Expression.(*ast.HashLiteral)
+	if !ok {
+		t.Fatalf("exp is not ast.HashLiteral. got=%T", stmt.Expression)
+	}
+
+	if len(hash.Pairs) != 3 {
+		t.Errorf("hash.Pairs has wrong length. got=%d", len(hash.Pairs))
+	}
+
+	tests := map[string]func(ast.Expression){
+		"one": func(e ast.Expression) {
+			testInfixExpression(t, e, 0, "+", 1)
+		},
+		"two": func(e ast.Expression) {
+			testInfixExpression(t, e, 10, "-", 8)
+		},
+		"three": func(e ast.Expression) {
+			testInfixExpression(t, e, 15, "/", 5)
+		},
+	}
+
+	for key, value := range hash.Pairs {
+		literal, ok := key.(*ast.StringLiteral)
+		if !ok {
+			t.Errorf("key is not ast.StringLiteral. got=%T", key)
+			continue
+		}
+
+		testFunc, ok := tests[literal.Value]
+		if !ok {
+			t.Errorf("no test function for key %q found", literal.Value)
+			continue
+		}
+
+		testFunc(value)
+	}
+}
diff --git a/tokens/tokens.go b/tokens/tokens.go
index aac82d3..e802c84 100644
--- a/tokens/tokens.go
+++ b/tokens/tokens.go
@@ -31,6 +31,7 @@ const (
 	// Delimiters
 	COMMA     = ","
 	SEMICOLON = ";"
+	COLON     = ":"
 
 	LPAREN   = "("
 	RPAREN   = ")"