Skip to content

Commit 3386b53

Browse files
cedrickcheecedrickchee
committed
4.5 Hash
* Lex hash literals * Parse hash literals * Hash objects * Evaluate hash literals * Evaluate index expressions with hashes
1 parent d3227c2 commit 3386b53

File tree

10 files changed

+519
-0
lines changed

10 files changed

+519
-0
lines changed

‎ast/ast.go‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -440,3 +440,31 @@ func (ie *IndexExpression) String() string {
440440

441441
return out.String()
442442
}
443+
444+
// HashLiteral represents a hash map or dictionary literal, a set of key/value
445+
// pairs.
446+
type HashLiteral struct {
447+
Token token.Token // the '{' token
448+
Pairs map[Expression]Expression
449+
}
450+
451+
func (hl *HashLiteral) expressionNode() {}
452+
453+
// TokenLiteral prints the literal value of the token associated with this node.
454+
func (hl *HashLiteral) TokenLiteral() string { return hl.Token.Literal }
455+
456+
// String returns a stringified version of the AST for debugging.
457+
func (hl *HashLiteral) String() string {
458+
var out bytes.Buffer
459+
460+
pairs := []string{}
461+
for key, value := range hl.Pairs {
462+
pairs = append(pairs, key.String()+":"+value.String())
463+
}
464+
465+
out.WriteString("{")
466+
out.WriteString(strings.Join(pairs, ", "))
467+
out.WriteString("}")
468+
469+
return out.String()
470+
}

‎evaluator/evaluator.go‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -143,6 +143,9 @@ func Eval(node ast.Node, env *object.Environment) object.Object {
143143
return index
144144
}
145145
return evalIndexExpression(left, index)
146+
147+
case *ast.HashLiteral:
148+
return evalHashLiteral(node, env)
146149
}
147150

148151
return nil
@@ -476,6 +479,8 @@ func evalIndexExpression(left, index object.Object) object.Object {
476479
switch {
477480
case left.Type() == object.ARRAY_OBJ && index.Type() == object.INTEGER_OBJ:
478481
return evalArrayIndexExpression(left, index)
482+
case left.Type() == object.HASH_OBJ:
483+
return evalHashIndexExpression(left, index)
479484
default:
480485
return newError("index operator not supported: %s", left.Type())
481486
}
@@ -496,3 +501,48 @@ func evalArrayIndexExpression(array, index object.Object) object.Object {
496501

497502
return arrayObject.Elements[idx]
498503
}
504+
505+
func evalHashLiteral(
506+
node *ast.HashLiteral,
507+
env *object.Environment,
508+
) object.Object {
509+
pairs := make(map[object.HashKey]object.HashPair)
510+
511+
for keyNode, valueNode := range node.Pairs {
512+
key := Eval(keyNode, env)
513+
if isError(key) {
514+
return key
515+
}
516+
517+
hashKey, ok := key.(object.Hashable)
518+
if !ok {
519+
return newError("unusable as hash key: %s", key.Type())
520+
}
521+
522+
value := Eval(valueNode, env)
523+
if isError(value) {
524+
return value
525+
}
526+
527+
hashed := hashKey.HashKey()
528+
pairs[hashed] = object.HashPair{Key: key, Value: value}
529+
}
530+
531+
return &object.Hash{Pairs: pairs}
532+
}
533+
534+
func evalHashIndexExpression(hash, index object.Object) object.Object {
535+
hashObject := hash.(*object.Hash)
536+
537+
key, ok := index.(object.Hashable)
538+
if !ok {
539+
return newError("unusable as hash key: %s", index.Type())
540+
}
541+
542+
pair, ok := hashObject.Pairs[key.HashKey()]
543+
if !ok {
544+
return NULL
545+
}
546+
547+
return pair.Value
548+
}

‎evaluator/evaluator_test.go‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -232,6 +232,14 @@ if (10 > 1) {
232232
"foobar",
233233
"identifier not found: foobar",
234234
},
235+
{
236+
`{"name": "Monkey"}[fn(x) { x }];`,
237+
"unusable as hash key: FUNCTION",
238+
},
239+
{
240+
`999[1]`,
241+
"index operator not supported: INTEGER",
242+
},
235243
}
236244

237245
for _, tt := range tests {
@@ -495,6 +503,92 @@ func TestArrayIndexExpressions(t *testing.T) {
495503
}
496504
}
497505

506+
func TestHashLiterals(t *testing.T) {
507+
input := `let two = "two";
508+
{
509+
"one": 10 - 9,
510+
two: 1 + 1,
511+
"thr" + "ee": 6 / 2,
512+
4: 4,
513+
true: 5,
514+
false: 6
515+
}`
516+
517+
evaluated := testEval(input)
518+
result, ok := evaluated.(*object.Hash)
519+
if !ok {
520+
t.Fatalf("Eval didn't return Hash. got=%T (%+v)", evaluated, evaluated)
521+
}
522+
523+
expected := map[object.HashKey]int64{
524+
(&object.String{Value: "one"}).HashKey(): 1,
525+
(&object.String{Value: "two"}).HashKey(): 2,
526+
(&object.String{Value: "three"}).HashKey(): 3,
527+
(&object.Integer{Value: 4}).HashKey(): 4,
528+
TRUE.HashKey(): 5,
529+
FALSE.HashKey(): 6,
530+
}
531+
532+
if len(result.Pairs) != len(expected) {
533+
t.Fatalf("Hash has wrong num of pairs. got=%d", len(result.Pairs))
534+
}
535+
536+
for expectedKey, expectedValue := range expected {
537+
pair, ok := result.Pairs[expectedKey]
538+
if !ok {
539+
t.Errorf("no pair for given key in Pairs")
540+
}
541+
542+
testIntegerObject(t, pair.Value, expectedValue)
543+
}
544+
}
545+
546+
func TestHashIndexExpressions(t *testing.T) {
547+
tests := []struct {
548+
input string
549+
expected interface{}
550+
}{
551+
{
552+
`{"foo": 5}["foo"]`,
553+
5,
554+
},
555+
{
556+
`{"foo": 5}["bar"]`,
557+
nil,
558+
},
559+
{
560+
`let key = "foo"; {"foo": 5}[key]`,
561+
5,
562+
},
563+
{
564+
`{}["foo"]`,
565+
nil,
566+
},
567+
{
568+
`{5: 5}[5]`,
569+
5,
570+
},
571+
{
572+
`{true: 5}[true]`,
573+
5,
574+
},
575+
{
576+
`{false: 5}[false]`,
577+
5,
578+
},
579+
}
580+
581+
for _, tt := range tests {
582+
evaluated := testEval(tt.input)
583+
integer, ok := tt.expected.(int)
584+
if ok {
585+
testIntegerObject(t, evaluated, int64(integer))
586+
} else {
587+
testNullObject(t, evaluated)
588+
}
589+
}
590+
}
591+
498592
func testEval(input string) object.Object {
499593
l := lexer.New(input)
500594
p := parser.New(l)

‎lexer/lexer.go‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,8 @@ func (l *Lexer) NextToken() token.Token {
4343
}
4444
case ';':
4545
tok = newToken(token.SEMICOLON, l.ch)
46+
case ':':
47+
tok = newToken(token.COLON, l.ch)
4648
case '(':
4749
tok = newToken(token.LPAREN, l.ch)
4850
case ')':

‎lexer/lexer_test.go‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ if (5 < 10) {
3131
"foobar"
3232
"foo bar"
3333
[1, 2];
34+
{"foo": "bar"}
3435
`
3536

3637
tests := []struct {
@@ -118,6 +119,11 @@ if (5 < 10) {
118119
{token.INT, "2"},
119120
{token.RBRACKET, "]"},
120121
{token.SEMICOLON, ";"},
122+
{token.LBRACE, "{"},
123+
{token.STRING, "foo"},
124+
{token.COLON, ":"},
125+
{token.STRING, "bar"},
126+
{token.RBRACE, "}"},
121127
{token.EOF, ""},
122128
}
123129

‎object/object.go‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ package object
77
import (
88
"bytes"
99
"fmt"
10+
"hash/fnv"
1011
"strings"
1112

1213
"github.com/cedrickchee/hou/ast"
@@ -39,8 +40,17 @@ const (
3940

4041
// ARRAY_OBJECT is the Array object type.
4142
ARRAY_OBJ = "ARRAY"
43+
44+
// HASH_OBJ is the Hash object type.
45+
HASH_OBJ = "HASH"
4246
)
4347

48+
// Hashable is the interface for all hashable objects which must implement the
49+
// HashKey() method which returns a HashKey result.
50+
type Hashable interface {
51+
HashKey() HashKey
52+
}
53+
4454
// BuiltinFunction represents the builtin function type.
4555
// It's the type definition of a callable Go function.
4656
type BuiltinFunction func(args ...Object) Object
@@ -202,3 +212,67 @@ func (ao *Array) Inspect() string {
202212

203213
return out.String()
204214
}
215+
216+
// HashKey represents a hash key object and holds the Type of Object hashed and
217+
// its hash value in Value.
218+
type HashKey struct {
219+
Type ObjectType
220+
Value uint64
221+
}
222+
223+
// HashKey returns a HashKey object.
224+
func (b *Boolean) HashKey() HashKey {
225+
var value uint64
226+
227+
if b.Value {
228+
value = 1
229+
} else {
230+
value = 0
231+
}
232+
233+
return HashKey{Type: b.Type(), Value: value}
234+
}
235+
236+
// HashKey returns a HashKey object.
237+
func (i *Integer) HashKey() HashKey {
238+
return HashKey{Type: i.Type(), Value: uint64(i.Value)}
239+
}
240+
241+
// HashKey returns a HashKey object.
242+
func (s *String) HashKey() HashKey {
243+
h := fnv.New64a()
244+
h.Write([]byte(s.Value))
245+
246+
return HashKey{Type: s.Type(), Value: h.Sum64()}
247+
}
248+
249+
// HashPair is an object that holds a key and value of type Object.
250+
type HashPair struct {
251+
Key Object
252+
Value Object
253+
}
254+
255+
// Hash is a hash map and holds a map of HashKey to HashPair(s).
256+
type Hash struct {
257+
Pairs map[HashKey]HashPair
258+
}
259+
260+
// Type returns the type of the object.
261+
func (h *Hash) Type() ObjectType { return HASH_OBJ }
262+
263+
// Inspect returns a stringified version of the object for debugging.
264+
func (h *Hash) Inspect() string {
265+
var out bytes.Buffer
266+
267+
pairs := []string{}
268+
for _, pair := range h.Pairs {
269+
pairs = append(pairs, fmt.Sprintf("%s: %s",
270+
pair.Key.Inspect(), pair.Value.Inspect()))
271+
}
272+
273+
out.WriteString("{")
274+
out.WriteString(strings.Join(pairs, ", "))
275+
out.WriteString("}")
276+
277+
return out.String()
278+
}

‎object/object_test.go‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package object
2+
3+
import "testing"
4+
5+
func TestStringHashKey(t *testing.T) {
6+
hello1 := &String{Value: "Hello World"}
7+
hello2 := &String{Value: "Hello World"}
8+
diff1 := &String{Value: "My name is johnny"}
9+
diff2 := &String{Value: "My name is johnny"}
10+
11+
if hello1.HashKey() != hello2.HashKey() {
12+
t.Errorf("strings with same content have different hash keys")
13+
}
14+
15+
if diff1.HashKey() != diff2.HashKey() {
16+
t.Errorf("strings with same content have different hash keys")
17+
}
18+
19+
if hello1.HashKey() == diff1.HashKey() {
20+
t.Errorf("strings with different content have same hash keys")
21+
}
22+
}
23+
24+
func TestBooleanHashKey(t *testing.T) {
25+
true1 := &Boolean{Value: true}
26+
true2 := &Boolean{Value: true}
27+
false1 := &Boolean{Value: false}
28+
false2 := &Boolean{Value: false}
29+
30+
if true1.HashKey() != true2.HashKey() {
31+
t.Errorf("trues do not have same hash key")
32+
}
33+
34+
if false1.HashKey() != false2.HashKey() {
35+
t.Errorf("falses do not have same hash key")
36+
}
37+
38+
if true1.HashKey() == false1.HashKey() {
39+
t.Errorf("true has same hash key as false")
40+
}
41+
}
42+
43+
func TestIntegerHashKey(t *testing.T) {
44+
one1 := &Integer{Value: 1}
45+
one2 := &Integer{Value: 1}
46+
two1 := &Integer{Value: 2}
47+
two2 := &Integer{Value: 2}
48+
49+
if one1.HashKey() != one2.HashKey() {
50+
t.Errorf("integers with same content have twoerent hash keys")
51+
}
52+
53+
if two1.HashKey() != two2.HashKey() {
54+
t.Errorf("integers with same content have twoerent hash keys")
55+
}
56+
57+
if one1.HashKey() == two1.HashKey() {
58+
t.Errorf("integers with twoerent content have same hash keys")
59+
}
60+
}

0 commit comments

Comments
 (0)