Receiving the value of an array

[zimmski]

I am implementing a symbolic execution for fun using Z3(master branch) as the constraint solver. Since there is no "String" sort I am trying to implement strings using an integer array. However, I cannot figure out how to receive the value of the array.

(set-option :produce-models true)
(declare-const ia (Array Int Int))
(assert (= ia (store (store (store (store ((as const(Array Int Int)) 0) 0 99) 1 111) 2 111) 3 108)))
(check-sat)
(get-value (ia))
(get-model)

Result:

sat
((ia (_ as-array k!4)))
(model 
  (define-fun ia () (Array Int Int)
    (_ as-array k!4))
  (define-fun k!3 ((x!1 Int)) Int
    (ite (= x!1 2) 111
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0))))
  (define-fun k!0 ((x!1 Int)) Int
    0)
  (define-fun k!4 ((x!1 Int)) Int
    (ite (= x!1 3) 108
    (ite (= x!1 2) 111
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0)))))
  (define-fun k!1 ((x!1 Int)) Int
    (ite (= x!1 0) 99
      0))
  (define-fun k!2 ((x!1 Int)) Int
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0)))
)

(Since I am new to SMTLib) is it correct that I have to note what the output of get-value is and then look up the correct value through get-model? Is there an easier way to receive the value of the array? I could not find anything useful via Google besides the Z3 guide http://rise4fun.com/z3/tutorialcontent/guide

Also, since this is all new to me. Is this the correct way of implementing a constraint for a string? Is there an easier way of defining an array? I would really appreciate it if you have some guidance or reading material for me.

[wintersteiger]

Through the SMT2 file-based interface there is no "easier" way; in general models for arrays are functions (maps) of indices to values. Some of our APIs try to make that a little bit easier by hiding the k! entries and resolving that link to the function, but that's not possible in SMT2. There have been many questions (and bug reports) about this on StackOverflow.

I don't think there is a "correct" way of implementing string constraints. This is subject of ongoing research and there are plans to create an SMT theory for strings, but that's still in a draft state I think.

[wintersteiger]

Closing this issue, please reopen if necessary.

[zimmski]

Thank you! Do you think that this will be addressed with a newer SMT-LIB version?

[wintersteiger]

Yes, all interested parties are already working on an SMT string logic and solvers. I don't know exactly who's leading the discussion, but I know that Cesare Tinelli knows :)

There is also a Z3-based string solver prototype, but AFAIK it's not available in source code yet. I'll notify those responsible to add any additional information here.

[zimmski]

Do you mean https://github.com/z3str/Z3-str ?

[wintersteiger]

No, that's an independent effort, but it's also based on Z3. I don't know about technical differences between the two, but I'm sure the authors would be happy to point those out.

[zimmski]

I have a working solution and I am working on some additional functionality around strings. I noticed something odd (at least odd to me) about Z3. When I take the example above and just negate the assertion, Z3 does not pick the empty array which would fulfill the assertion. For example this SMTLIB

(set-option :produce-models true)
(declare-const a (Array Int Int))
(assert (not (= a (store (store (store (store ((as const(Array Int Int)) 0) 0 99) 1 111) 2 111) 3 108))))
(check-sat)
(get-value (a))
(get-model)

prints the following

sat
((a (_ as-array k!0)))
(model 
  (define-fun a () (Array Int Int)
    (_ as-array k!0))
  (define-fun k!3 ((x!1 Int)) Int
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0)))
  (define-fun k!0 ((x!1 Int)) Int
    (ite (= x!1 1) 5
      4))
  (define-fun k!4 ((x!1 Int)) Int
    (ite (= x!1 2) 111
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0))))
  (define-fun k!1 ((x!1 Int)) Int
    0)
  (define-fun k!5 ((x!1 Int)) Int
    (ite (= x!1 3) 108
    (ite (= x!1 2) 111
    (ite (= x!1 1) 111
    (ite (= x!1 0) 99
      0)))))
  (define-fun k!2 ((x!1 Int)) Int
    (ite (= x!1 0) 99
      0))
)

So get-value suggests that k!0 should be used which is the array [4, 5]. Why does Z3 use the "odd" numbers [4, 5]? And why does Z3 not suggest the empty array of k!1? Also k!0 to k!4 could be used as witnesses but not k!5. So I am wondering why k!5 in the model at all? Is there a paper on this behavior or should I dive into the Z3 source code to get a better understanding?