Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

PLE produces incorrect equalities #496

Open
facundominguez opened this issue Oct 7, 2021 · 9 comments · Fixed by #498
Open

PLE produces incorrect equalities #496

facundominguez opened this issue Oct 7, 2021 · 9 comments · Fixed by #498

Comments

@facundominguez
Copy link
Collaborator

Verification of the following example succeeds when constraints 1 and 3 are actually unsafe.

// test.fq
define f(lq1:a) : a = { lq1 }

expand [1 : True; 2 : True; 3 : True; 4 : True]

bind 0 f : {v : func(1,[@(0);@(0)]) | []}
bind 1 x : {v : int | []}
bind 2 y : {v : int | x = 0}
bind 3 z : {v : int | x = 1}
bind 4 w : {v : int | f(x) = 0}
      
constraint:
  env [0;1;2;4]
  lhs {v : int | true}
  rhs {v : int | false }
  id 1 tag []

constraint:
  env [0;1;3;4]
  lhs {v : int | true}
  rhs {v : int | false}
  id 2 tag []

constraint:
  env [0;1;2;4]
  lhs {v : int | true}
  rhs {v : int | false }
  id 3 tag []

constraint:
  env [0;1;3;4]
  lhs {v : int | true}
  rhs {v : int | false }
  id 4 tag []

Verify with

$ fixpoint --eliminate=some --rewriteaxioms test.fq

Liquid-Fixpoint Copyright 2013-21 Regents of the University of California.
All Rights Reserved.

Working  80% [====================================================.............]
Working 180% [=====================================================================================================================]

fromList
  [ (1,PAnd [])
  , (4,PAtom Eq (EApp (EVar "f") (EVar "x")) (ECon (I 1)))
  , (5,PAtom Eq (EApp (EVar "f") (EVar "x")) (ECon (I 0)))
  , (6,PAtom Eq (EApp (EVar "f") (EVar "x")) (ECon (I 1)))
  , (7,PAtom Eq (EApp (EVar "f") (EVar "x")) (ECon (I 0)))
  , (8,PAtom Eq (EApp (EVar "f") (EVar "x")) (ECon (I 1)))
  ]

Safe ( 4  constraints checked)

I modified liquid-fixpoint to print the assignments of discovered equations to bindings as shown above.

I think the problem is that different constraints produce different equations for binding 4, and they all compete to assign their equations to the same binding in the output of PLE.

Fixing this will probably require to add new bindings to each constraint, rather than attempting to modify the existing bindings.
@ranjitjhala
Copy link
Member

ranjitjhala commented Oct 7, 2021 via email

@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 7, 2021 •
edited

If two constraints both have binders i and j they have the same set of binders between i and j.

Ah, in that case, the current situation is still problematic.

  1. The software or human interacting with liquid-fixpoint gets no feedback that the invariant is broken
  2. I don't think liquid-fixpoint is maintaining this invariant internally. At least environment reduction would eliminate redundant bindings without considering it.
  3. It doesn't look like an algorithm to establish the invariant exists without duplicating bindings. Say we have constraints with bindings [1;2;3;4], [1;2;4], [1;3;4]. These can't be organized tree-like without duplicating and reordering constraints. Maybe: [1;4;old_2;old_3], [1;4;old_2], [1;4;copy_of_3]. Perhaps we can reduce the damage by choosing wisely what bindings to duplicate, and maybe the Trie deserves this complexity, but it looks a bit too much to push to the users.

@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 7, 2021 •
edited

If two constraints both have binders i and j they have the same set of binders between i and j.

Also, it is worth noting that this invariant doesn't affect correctness of the core of PLE itself. If the invariant doesn't hold, PLE will just duplicate some effort analyzing some bindings more than once.

The thing that breaks is the way in which equalities are collected. Whether a Trie or some other data structure is used, is of little consequence if the algorithm is forced to deliver new equalities per binding instead of per constraint.

@ranjitjhala
Copy link
Member

Hi @facundominguez -- sorry I was putting out some other fires :-)

First, in this case, here's the duplicated variant which respects the "trie invariant" by cloning 4 as 40:

// test.fq
define f(lq1:a) : a = { lq1 }

expand [1 : True; 2 : True; 3 : True; 4 : True]

bind 0 f : {v : func(1,[@(0);@(0)]) | []}
bind 1 x : {v : int | []}
bind 2 y : {v : int | x = 0}
bind 3 z : {v : int | x = 1}
bind 4 w : {v : int | f(x) = 0}
bind 40 w : {v : int | f(x) = 0}

constraint:
  env [0;1;2;4]
  lhs {v : int | true}
  rhs {v : int | false }
  id 1 tag []

constraint:
  env [0;1;3;40]
  lhs {v : int | true}
  rhs {v : int | false}
  id 2 tag []

constraint:
  env [0;1;2;4]
  lhs {v : int | true}
  rhs {v : int | false }
  id 3 tag []

constraint:
  env [0;1;3;40]
  lhs {v : int | true}
  rhs {v : int | false }
  id 4 tag []

Now I get:

$ fixpoint --eliminate=some --rewriteaxioms T496.fq
...
Unsafe:
WARNING: 1
WARNING: 3

Second, the goal of the trie is precisely to

  1. Represent all the constraints with shared binders,
  2. Compute (PLE) equalities per binder, which allows
  3. Sharing the equalities across all constraints that use those binders.

It is better to do it per binder than constraint because (2) ensures the binders
are shared across constraints. For example, consider two constraints:

Env |- f(x) = 0
Env |- f(y) = 10

Now if the Env is shared we want to just compute the PLE equalities once, and not duplicate work across the two constraints, which is what the trie is doing.

Does that make sense?

[The pre-trie version computed equalities per-constraint and was way slower]

@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 8, 2021 •
edited

Does that make sense?

I think I follow this far. Though I'm not proposing to eliminate the trie, I'm just saying that the discovered equalities shouldn't be collapsed into a single map of bindings to equalities (i.e. the InstRes type in the implementation).

When the constraints are tree like, bindings are shared and no work is duplicated. And when the constraints aren't tree like, it is just slower, but still yields correct equalities for each constraint. After all, your own fixup is cloning the bindings which creates more work for PLE anyway.

sorry I was putting out some other fires :-)

That's alright. We can get back to this when you have the availability. Could have a call as well about it.

@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 11, 2021 •
edited

Here goes an attempt at explaining a fix. I'm proposing to eliminate the tree-like invariant. PLE will continue to be as fast as today if the invariant holds. And when the invariant doesn't hold, PLE will become as slow as the fixup that duplicates bindings as necessary to establish the invariant again.

Simplifying many details, the current PLE works schematically as follows:

type Trie = [Branch]
data Branch = Branch BindId Trie | Val ConstraintId

ple :: (Bindings, Constraints) -> Bindings
ple (bs, cs) = updateBindings bs $ equalitiesFromTrie $ buildTrie cs

updateBindings :: Bindings -> HashMap BindId EqualitySet -> Bindings
updateBindings bs eqs = [ (b, rhs && (eqs ! b)) | (b, rhs) <- bs]

equalitiesFromTrie :: Trie -> HashMap BindId EqualitySet
equalitiesFromTrie = mconcat . map pleBranch

-- | This goes into the details of producing the actual equalities and may
-- call in mutual recursion to 'equalitiesFromTrie'.
pleBranch :: Trie -> HashMap BindId EqualitySet

buildTrie :: Constraints -> Trie

As the multiple HashMaps are merged, there is no check that the entries on one HashMap don't overwrite the entries in another. We could change this algorithm to give it a richer output so when the HashMaps do have colliding keys, all the values are preserved.

- equalitiesFromTrie :: Trie -> HashMap BindId EqualitySet
+ equalitiesFromTrie :: Trie -> HashMap BindId [(EqualitySet, HashSet ConstraintId)]

Now, whenever a binding is assigned equalities on different branches of the trie, each branch originates a new item in the list.

- equalitiesFromTries = mconcat . map pleBranch
+ equalitiesFromTries = unionsWith (++) . map pleBranch

Rather than overwriting one with another, the discovered equalities are kept together. The set of constraints (i.e. the second component of (EqualitySet, HashSet ConstraintId)) explains for which constraints the equalities apply. An invariant of the enriched output is that the constraints sets for a given binding are disjoint. More formally:

forall (b :: BindId) (cs :: Constraints).
  allDisjoint (map snd (equalitiesFromTrie (buildTrie cs) ! b))

allDisjoint [] = True
allDisjoint (x : xs) = all (null . intersection x) xs && allDisjoint xs

When we update the bindings, we duplicate the bindings for each equality set that has been produced.

updateBindings
  :: Bindings
  -> HashMap BindId [(EqualitySet, HashSet ConstraintId)]
  -> (Bindings, [(BindId, HashSet ConstraintId)]) -- updated bindings + new bindids to insert in some constraints

@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 23, 2021 •
edited

Some tests in LiquidHaskell fail if we check that joint points in the trie do not occur on separate branches (here's the patch: a0f2dc9). All the tests I tried pass if I disable environment reduction.

This was referenced Oct 24, 2021
Merged
Merged
@facundominguez
Copy link
Collaborator Author

facundominguez commented Oct 27, 2021 •
edited

Interesting. Github doesn't let me reopen this issue.

@ranjitjhala ranjitjhala reopened this Oct 27, 2021
@ranjitjhala
Copy link
Member

Oops! Just reopened

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Check the tree like invariant facundominguez/liquid-fixpoint
2 participants
@facundominguez @ranjitjhala