8000 seq issues - running · Issue #5591 · Z3Prover/z3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

seq issues - running #5591

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
Closed
NikolajBjorner opened this issue Oct 12, 2021 · 10 comments
Closed

seq issues - running #5591

NikolajBjorner opened this issue Oct 12, 2021 · 10 comments
Assignees
@NikolajBjorner @veanes
Labels
string

Comments

@NikolajBjorner
Copy link
Contributor
NikolajBjorner commented Oct 12, 2021 •
edited
Loading

accumulated issues for seq
@NikolajBjorner
Copy link
Contributor Author
NikolajBjorner commented Oct 12, 2021 •
edited
Loading

an instance involving nth

(set-option :rewriter.eq2ineq true)
(declare-fun z () Int)
(declare-fun b () (Seq Int))
(declare-fun y () Int)
(declare-fun a () (Seq Int))
(declare-fun x () Int)
(assert (and (= 1 z) (distinct (seq.nth b x) (seq.nth a z)) (= (seq.nth b y) (seq.nth b 1))))
(assert (> x 0))
(assert (> z 0))
(check-sat)

@NikolajBjorner
Copy link
Contributor Author
NikolajBjorner commented Oct 12, 2021 •
edited
Loading

Solution unsoundness:

[556] % cvc5 -q --strings-exp small.smt2
unsat
[557] % z3release model_validate=true small.smt2
sat
(error "line 3 column 10: an invalid model was generated")
[558] % cat small.smt2
(declare-fun a () String)
(assert (str.in_re (str.++ a "AA") (re.++ (re.* (str.to_re "B")) (str.to_re (str.substr (str.++ "B" a) (str.len a) (str.len a))))))
(check-sat)
[559] %

@veanes - this is so far the only remaining regex bug in this thread.

@NikolajBjorner NikolajBjorner mentioned this issue Oct 12, 2021
Closed
NikolajBjorner added a commit that referenced this issue Oct 12, 2021
@NikolajBjorner
#5591
9a76bf0 
nth issue
@NikolajBjorner
Copy link
Contributor Author 
(declare-fun z () (Seq Bool))
(assert (not (seq.nth (as seq.empty (Seq Bool)) 0)))
(assert (seq.nth (seq.extract z 1 (- (seq.len z) 1)) 0))
(check-sat)

@zhendongsu
Copy link

Invalid model:

[543] % z3release model_validate=true small.smt2
sat
(error "line 3 column 10: an invalid model was generated")
(
  (define-fun a () String
    "B")
)
[544] % 
[544] % cat small.smt2
(declare-fun a () String)
(assert (= (= a "") (str.in_re a (re.range "A" a))))
(check-sat)
(get-model)
[545] %

@zhendongsu
Copy link

Refutation unsoundness:

[534] % z3release small.smt2
unsat
sat
[535] % cat small.smt2
(declare-fun a () String)
(assert (str.in_re (str.replace (str.++ a "B") "B" "A") (re.* (re.+ (re.range "A" (str.replace "A" (str.++ a "B") ""))))))
(check-sat)
(reset)
(define-fun a () String "")
(assert (str.in_re (str.replace (str.++ a "B") "B" "A") (re.* (re.+ (re.range "A" (str.replace "A" (str.++ a "B") ""))))))
(check-sat)
[536] %

@zhendongsu
Copy link

Refutation unsoundness (might be related to #5591 (comment), but simpler):

[562] % z3release small.smt2
unsat
[563] % cvc5 -q small.smt2
sat
[564] % cat small.smt2
(declare-fun a () String)
(assert (str.in_re "A" (re.range "A" (str.replace "A" (str.++ a "B") ""))))
(check-sat)
[565] %

@zhendongsu
Copy link

Another refutation unsoundness instance:

[520] % z3release small.smt2
unsat
[521] % cvc5 -q small.smt2
sat
[522] % cat small.smt2
(declare-fun a () String)
(assert (str.in_re a (re.inter (re.range a "B") (str.to_re "A"))))
(check-sat)
[523] %

@zhendongsu
Copy link

Another likely related refutation unsoundness instance:

[517] % z3release small.smt2
unsat
[518] % cvc5 -q small.smt2
sat
[519] % cat small.smt2
(declare-fun a () String)
(assert (str.in_re a (re.inter (re.opt (re.range a a)) (str.to_re "A"))))
(check-sat)
[520] %

NikolajBjorner added a commit that referenced this issue Oct 14, 2021
@NikolajBjorner
#5591
f60ed2c
@zhendongsu
Copy link

Invalid model (possibly related to the other instances also involving re.range):

[568] % z3release model_validate=true small.smt2
sat
(error "line 3 column 10: an invalid model was generated")
(
  (define-fun a () String
    "A")
)
[569] % cat small.smt2
(declare-fun a () String)
(assert (not (str.in_re a (re.range a a))))
(check-sat)
(get-model)
[570] %

@zhendongsu
Copy link

Another invalid model instance:

[540] % z3release model_validate=true small.smt2
sat
(error "line 4 column 10: an invalid model was generated")
(
  (define-fun a () String
    "BC")
)
[541] % cat small.smt2
(declare-fun a () String)
(assert (= (str.len a) 2))
(assert (not (str.in_re (str.at a 0) (re.range "A" (str.at a 1)))))
(check-sat)
(get-model)
[542] %

This was referenced Oct 15, 2021
Merged
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@NikolajBjorner NikolajBjorner

@veanes veanes

Labels
string
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@NikolajBjorner @zhendongsu @veanes
0