(t *testing.T)
| 23 | ) |
| 24 | |
| 25 | func TestShortestPaths(t *testing.T) { |
| 26 | store := factstore.NewSimpleInMemoryStore() |
| 27 | clauses := []ast.Clause{ |
| 28 | clause("edge(/a, /b)."), |
| 29 | clause("edge(/b, /c)."), |
| 30 | clause("edge(/c, /d)."), |
| 31 | clause("edge(/a, /d)."), |
| 32 | |
| 33 | // The shortest_path relation. |
| 34 | clause("shortest_path(X, Y, [Y, X]) :- edge(X, Y)."), |
| 35 | clause("shortest_path(X, Z, NewPath) :- " + |
| 36 | "shortest_path(X, Y, Path), edge(Y, Z) |> let NewPath = fn:list:cons(Z, Path)."), |
| 37 | |
| 38 | // The merge predicate. This returns the join (least-upper bound) |
| 39 | // of P1 and P2 in P. It need not be datalog (P is not bound), since |
| 40 | // it is evaluated top-down. |
| 41 | clause("shorter(P1, P2, P) :- fn:list:len(P1) < fn:list:len(P2), P = P1."), |
| 42 | clause("shorter(P1, P2, P) :- fn:list:len(P2) <= fn:list:len(P1), P = P2."), |
| 43 | } |
| 44 | |
| 45 | // We need to declare two things to enable custom joins: |
| 46 | // - a functional dependency: X, Y determine P. |
| 47 | // - a merge predicate name that provides the lattice-join operation. |
| 48 | shortestPathDecl, err := ast.NewDecl(atom("shortest_path(X, Y, P)"), []ast.Atom{ |
| 49 | atom("fundep([X, Y], [P])"), |
| 50 | atom("merge([P], 'shorter')"), |
| 51 | }, nil, nil) |
| 52 | if err != nil { |
| 53 | t.Fatal(err) |
| 54 | } |
| 55 | |
| 56 | // The merge predicate is marked deferred(). Such predicates have to come |
| 57 | // with a mode declaration that specifies what the inputs and outputs are. |
| 58 | // Merge predicates in particular must have mode('+', '+', '-'). |
| 59 | shorterDecl, err := ast.NewDecl(atom("shorter(P1, P2, P)"), []ast.Atom{ |
| 60 | atom("mode('+', '+', '-')"), |
| 61 | atom("deferred()"), |
| 62 | }, nil, nil) |
| 63 | if err != nil { |
| 64 | t.Fatal(err) |
| 65 | } |
| 66 | decls := []ast.Decl{shortestPathDecl, shorterDecl} |
| 67 | if err := analyzeAndEvalProgramWithDecls(t, clauses, decls, store); err != nil { |
| 68 | t.Errorf("Program evaluation failed %v program %v", err, program) |
| 69 | return |
| 70 | } |
| 71 | wantShortPath, err := functional.EvalAtom(atom("shortest_path(/a, /d, [/d, /a])"), nil) |
| 72 | if err != nil { |
| 73 | t.Fatal(err) |
| 74 | } |
| 75 | if !store.Contains(wantShortPath) { |
| 76 | t.Errorf("store does not contain %v that is shortest: %v", wantShortPath, store) |
| 77 | } |
| 78 | notWantLongPath, err := functional.EvalAtom(atom("shortest_path(/a, /d, [/d, /c, /b, /a])"), nil) |
| 79 | if err != nil { |
| 80 | t.Fatal(err) |
| 81 | } |
| 82 | if store.Contains(notWantLongPath) { |
nothing calls this directly
no test coverage detected