A lesson in hashing - don't store objects in Hashmaps
This is just a bug that I found recently. I was working on semantic analysis on my resolver for my interpreter.
➜ cat right.lox
for (var a = 0; a < 1
; a = a + 1) {
print a;
}
➜ cat test.lox
for (var a = 0; a < 1; a = a + 1) {
print a;
}
These are the 2 different files that I'll be using. Both of them should print out 0 and then it quits....right? No, the bottom one fails and the top one succeeds.
You might say, well since there's a bug, you might have produced the AST differently, it could be that?
No. It's the same.
➜ /tmp/lox-interpreter-build/release/lox-interpreter parse right.lox
(Block Statement (Literal 0.0)(If Statement (Binary < (Variable <ident a>) (Literal 1.0)) (Block Statement (Block Statement Print (Variable <ident a>))(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0)))) ))
➜ /tmp/lox-interpreter-build/release/lox-interpreter parse test.lox
(Block Statement (Literal 0.0)(If Statement (Binary < (Variable <ident a>) (Literal 1.0)) (Block Statement (Block Statement Print (Variable <ident a>))(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0)))) ))
You can cross check it if you want, but it's the exact same AST. The actual culprit is this line.
self.locals.insert(expr.clone(), depth);
expr.clone() produces different hashes even if they're the same expression, SOMETIMES.
SOMETIMES
When you run test.lox, it will somehow generate the same AST for depth 0 and depth 1.
➜ /tmp/lox-interpreter-build/release/lox-interpreter run test.lox
Hash for expr (Variable <ident a>) @ depth 0: 1809391697895006775
Hash for expr (Variable <ident a>) @ depth 2: 2318077243996479372
Hash for expr (Variable <ident a>) @ depth 1: 1809391697895006775
Hash for expr (Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) @ depth 1: 4950619014970994726
Found var <ident a> @ depth 1
Current state of locals => [(Variable <ident a>) - 1]
[(Variable <ident a>) - 2]
[(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) - 1]
[line 1] Interpreter Error: Undefined Variable : a
Which causes an error, because depth 0 should have stayed as it's the top most scope. So any variable in that scope, where it should have been valid, will be considered invalid.
On the right.lox side of things, the hashes it produces are all different, so self.locals will keep the depth 0 of <ident a>, which will let it succeed the run.
➜ /tmp/lox-interpreter-build/release/lox-interpreter run right.lox
Hash for expr (Variable <ident a>) @ depth 0: 1809391697895006775
Hash for expr (Variable <ident a>) @ depth 2: 8788585497914714291
Hash for expr (Variable <ident a>) @ depth 1: 2318077243996479372
Hash for expr (Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) @ depth 1: 15583953087313941367
Found var <ident a> @ depth 0
Current state of locals => [(Variable <ident a>) - 2]
[(Variable <ident a>) - 1]
[(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) - 1]
[(Variable <ident a>) - 0]
Found var <ident a> @ depth 2
Current state of locals => [(Variable <ident a>) - 2]
[(Variable <ident a>) - 1]
[(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) - 1]
[(Variable <ident a>) - 0]
0
Found var <ident a> @ depth 1
Current state of locals => [(Variable <ident a>) - 2]
[(Variable <ident a>) - 1]
[(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) - 1]
[(Variable <ident a>) - 0]
Found var <ident a> @ depth 0
Current state of locals => [(Variable <ident a>) - 2]
[(Variable <ident a>) - 1]
[(Assignment <ident a> = (Binary + (Variable <ident a>) (Literal 1.0))) - 1]
[(Variable <ident a>) - 0]
Turns out, the reason why two of them generated the same hash was because they had the exact same metadata, which was <ident a>, line: 0.
Had to end up making an ID system for all my tokens so they all get a unique Id.
self.locals.entry(expr.clone()).or_insert(depth);
Have a good day and thanks for reading my vent.
Here's the commit if anyone want's to check: Git commit @ AmirAbdRazak/rlox
You just have to run ./run_interpreter.sh run test.lox.
And have test.lox look like this on the root.
for (var a = 0; a < 1; a = a + 1) {
print a;
}