z3 正则表达式排序无法识别

Question

我在以下 z3 查询中使用了正则表达式（出于其他原因也在 post 上编辑了 GitHub/z3/issues）并且在定义正则表达式排序时遇到了一些问题：

(declare-const dst            String)
(declare-const src            String)
;(declare-const zero           Regex)
;(declare-const one            Regex)
;(declare-const zero_or_one    Regex)
;(declare-const binary_strings Regex)

(assert (= (str.len dst) 25))
(assert (= (str.len src) 50))

;(assert (= zero           (str.to.re "\x00" )))
;(assert (= one            (str.to.re "\x01" )))
;(assert (= zero_or_one    (re.union zero one)))
;(assert (= binary_strings (re.* zero_or_one )))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [0] This doesn't work ...                      ;
;     probably got the Regex sort word wrong ... ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;(assert (str.in.re src binary_strings))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [1] This actually increases running times: ;
;     from 2 sec to 28 sec (!??)             ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;(assert (str.in.re src (re.* (re.union (str.to.re "\x00") (str.to.re "\x01")))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [2] This further increase running times from 2 sec to 57 sec ;
;     though it is semantically equivalent to [1] (?!?)        ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(assert (str.in.re src (re.* (re.range "\x00" "\x01"))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [3] original query takes 2 sec for the 25:50 pair ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(assert (< (str.len dst) (str.indexof src "\x00" 0)))

(check-sat)
(get-value (dst src))

我在这里做错了什么？谢谢！

编辑：（所以机器人不允许我编辑，因为这个 post 主要是代码，所以我最好添加一些这样的文本行。也许还有这样一行）不管怎样，方法是这样的：

(declare-const dst            String)
(declare-const src            String)

(define-fun one  () (RegEx String) (str.to.re "\x01"))
(define-fun zero () (RegEx String) (str.to.re "\x00"))

(define-fun zero_or_one    () (RegEx String) (re.union zero one))
(define-fun binary_strings () (RegEx String) (re.* zero_or_one ))

(assert (= (str.len dst) 25))
(assert (= (str.len src) 50))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [0] This does work ...                         ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(assert (str.in.re src binary_strings))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; [1] this query takes 25 sec                       ;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(assert (< (str.len dst) (str.indexof src "\x00" 0)))

(check-sat)
(get-value (dst src))

正确答案是：

sat
((dst "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00")
 (src "\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x00\x01\x00\x01\x00\x01\x00\x00\x00\x01\x00\x00\x00\x00\x01\x01\x00\x01\x01\x01\x00\x00"))

Answer 1

你可以这样写：

(define-fun zero () (RegEx String) (str.to.re "\x00"))

请注意，当前不支持比较正则表达式或将它们用作变量的决策过程。

z3 正则表达式排序无法识别

z3 Regex sort unrecognized

regex

smt

z3