A Trie.filter() Bug

Developers Language Support
1

Code:

import Trie "mo:base/Trie";
import Hash "mo:base/Hash";
import Nat "mo:base/Nat";

shared actor class Test() = this {
    type Status = {#Prepared; #Cancelled; #Opening; #Closing; #Closed; };
    type Value = {
        value: Nat; 
        status: Status;
    };
    private func keyn(t: Nat) : Trie.Key<Nat> { 
        return { key = t; hash = Hash.hash(t) }; 
    };
    private stable var trie1: Trie.Trie<Nat, Value> = Trie.empty();

    trie1 := Trie.put(trie1, keyn(31), Nat.equal, {value=10; status=#Cancelled;}).0;
    trie1 := Trie.put(trie1, keyn(36), Nat.equal, {value=11; status=#Opening;}).0;
    trie1 := Trie.put(trie1, keyn(30), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(28), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(25), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(24), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(22), Nat.equal, {value=11; status=#Opening;}).0;
    trie1 := Trie.put(trie1, keyn(21), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(35), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(33), Nat.equal, {value=10; status=#Cancelled;}).0;
    trie1 := Trie.put(trie1, keyn(34), Nat.equal, {value=10; status=#Cancelled;}).0;
    trie1 := Trie.put(trie1, keyn(32), Nat.equal, {value=10; status=#Cancelled;}).0;
    trie1 := Trie.put(trie1, keyn(29), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(27), Nat.equal, {value=11; status=#Opening;}).0;
    trie1 := Trie.put(trie1, keyn(26), Nat.equal, {value=12; status=#Closed;}).0;
    trie1 := Trie.put(trie1, keyn(23), Nat.equal, {value=12; status=#Closed;}).0;

    public query func test() : async (Nat, Nat, Nat, Nat){
        let temp1 = Trie.filter(trie1, func(k:Nat, v:Value):Bool{ v.status == #Opening });
        let temp2 = Trie.filter(trie1, func(k:Nat, v:Value):Bool{ v.status != #Opening });
        let temp3 = Trie.filter(trie1, func(k:Nat, v:Value):Bool{ v.status == #Opening or v.status != #Opening });
        let temp4 = Trie.filter(trie1, func(k:Nat, v:Value):Bool{ true });
        return (Trie.size(temp1), Trie.size(temp2), Trie.size(temp3), Trie.size(temp4));
    };
};

Execution of test() returns:

(0 : nat, 13 : nat, 16 : nat, 16 : nat)

The correct result SHOULD be (3 : nat, 13 : nat, 16 : nat, 16 : nat).
Trie.filter() may have a bug when traversing over keys.

The Environment:

  • Mac
  • dfx 0.9.3
  • network: ic
1 Like
2

I recommend reporting this at Issues · dfinity/motoko-base · GitHub

3

Thanks for the excellent bug report! I’ll file an issue and hope to get this fixed soon.

4

This will be fixed: Fix #369 by ggreif · Pull Request #371 · dfinity/motoko-base · GitHub

The next release will contain a fix, but in the interim feel free to apply the patch manually and verify the result.

Thanks again for the report!

4 Likes