Class: Udb::Z3ParameterTerm

Inherits:
Object
  • Object
show all
Extended by:
T::Sig
Defined in:
lib/udb/z3.rb

Overview

represent a parameter in Z3 There will only ever be one parameter term per parameter When a parameter term is constructed, it adds all relevant assertions to the solver

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(name, solver, schema_hsh)

Parameters:

  • name (String)
  • solver (Z3Solver)
  • schema_hsh (Hash{String => T.untyped}) 


329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
 
# File 'lib/udb/z3.rb', line 329

def initialize(name, solver, schema_hsh)
  @name = name
  @solver = solver

  case Z3ParameterTerm.detect_type(schema_hsh)
  when :int
    @term = Z3.Bitvec(name, 64)   # width doesn't matter here, so just make it large
    Z3ParameterTerm.constrain_int(@solver, @term, schema_hsh)
  when :boolean
    @term = Z3.Bool(name)
    Z3ParameterTerm.constrain_bool(@solver, @term, schema_hsh)
  when :string
    @term = Z3.Int(name)
    Z3ParameterTerm.constrain_string(@solver, @term, schema_hsh)
  when :array
    case Z3ParameterTerm.detect_array_subtype(schema_hsh)
    when :int
      @term = Z3FiniteArray.new(@solver, name, Z3::BitvecSort, schema_hsh.fetch("maxItems"), bitvec_width: 64)
      Z3ParameterTerm.constrain_array(@solver, @term, schema_hsh, Z3ParameterTerm.method(:constrain_int))
    when :boolean
      @term = Z3FiniteArray.new(@solver, name, Z3::BoolSort, schema_hsh.fetch("maxItems"))
      Z3ParameterTerm.constrain_array(@solver, @term, schema_hsh, Z3ParameterTerm.method(:constrain_bool))
    when :string
      @term = Z3FiniteArray.new(@solver, name, Z3::IntSort, schema_hsh.fetch("maxItems"))
      Z3ParameterTerm.constrain_array(@solver, @term, schema_hsh, Z3ParameterTerm.method(:constrain_string))
    else
      raise "TODO"
    end
    @idx_term = Z3.Int("#{name}_idx")
    @max_items = schema_hsh.fetch("maxItems")
    solver.assert @idx_term >= 0
    solver.assert @idx_term < @max_items
  end
end

Class Method Details

.constrain_array(solver, term, schema_hsh, subtype_constrain)

This method returns an undefined value.

assert all constraints for an array parameter

Parameters:

  • solver (Z3Solver)
  • term (Z3FiniteArray)
  • schema_hsh (Hash{String => T.untyped})
  • subtype_constrain (Method) 


179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
 
# File 'lib/udb/z3.rb', line 179

def self.constrain_array(solver, term, schema_hsh, subtype_constrain)
  if schema_hsh.key?("items")
    if schema_hsh.fetch("items").is_a?(Array)
      schema_hsh.fetch("items").each_with_index do |item_schema, idx|
        t = term[idx]
        subtype_constrain.call(solver, t, item_schema)
      end
    elsif schema_hsh.fetch("items").is_a?(Hash)
      max = schema_hsh.fetch("maxItems")
      (0..max).each do |idx|
        subtype_constrain.call(solver, term[idx], schema_hsh.fetch("items"))
      end
    else
      raise "unexpected"
    end
  end

  if schema_hsh.key?("additionalItems") && schema_hsh.fetch("additionalItems") != false
    min = 0
    max = nil
    if schema_hsh.key?("items")
      min = schema_hsh.fetch("items").size
    end
    if schema_hsh.key?("minItems")
      min = schema_hsh.fetch("minItems")
    end
    if schema_hsh.key?("maxItems")
      max = schema_hsh.fetch("maxItems")
    end
    raise "No max" if max.nil?

    ((min - 1)...max).each do |idx|
      subtype_constrain.call(solver, term[idx], schema_hsh.fetch("additionalItems"))
    end
  end

  if schema_hsh.key?("contains")
    max = schema_hsh.fetch("maxItems")
    subtype_constrain.call(solver, term[0], schema_hsh.fetch("contains"))
    (1..max).each do |i|
      subtype_constrain.call(solver, term[i], schema_hsh.fetch("contains"))
    end
  end

  if schema_hsh.key?("unique")
    max = schema_hsh.fetch("maxItems")
    Z3.Distinct(max.times.map { |i| term[i] })
  end

  if schema_hsh.key?("anyOf")
    raise "TODO"
  end

  if schema_hsh.key?("oneOf")
    raise "TODO"
  end

  if schema_hsh.key?("noneOf")
    raise "TODO"
  end

  if schema_hsh.key?("if")
    raise "TODO"
  end
end

.constrain_bool(solver, term, schema_hsh)

This method returns an undefined value.

assert all constraints for a boolean parameter

Parameters:

  • solver (Z3Solver)
  • term (Z3::BoolExpr)
  • schema_hsh (Hash{String => T.untyped}) 


114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
 
# File 'lib/udb/z3.rb', line 114

def self.constrain_bool(solver, term, schema_hsh)
  if schema_hsh.key?("const")
    solver.assert(term == schema_hsh.fetch("const"))
  end

  if schema_hsh.key?("allOf")
    constrain_bool(solver, term, schema_hsh.fetch("allOf"))
  end

  if schema_hsh.key?("anyOf")
    raise "TODO"
  end

  if schema_hsh.key?("oneOf")
    raise "TODO"
  end

  if schema_hsh.key?("noneOf")
    raise "TODO"
  end

  if schema_hsh.key?("if")
    raise "TODO"
  end
end

.constrain_int(solver, term, schema_hsh)

This method returns an undefined value.

assert all constraints for an integer parameter

Parameters:

  • solver (Z3Solver)
  • term (Z3::BitvecExpr)
  • schema_hsh (Hash{String => T.untyped}) 


58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
 
# File 'lib/udb/z3.rb', line 58

def self.constrain_int(solver, term, schema_hsh)
  if schema_hsh.key?("const")
    solver.assert(term == schema_hsh.fetch("const"))
  end

  if schema_hsh.key?("enum")
    expr = (term == schema_hsh.fetch("enum")[0])
    schema_hsh.fetch("enum")[1..].each do |v|
      expr = expr | (term == v)
    end
    solver.assert expr
  end

  if schema_hsh.key?("minimum")
    solver.assert term.unsigned_ge(schema_hsh.fetch("minimum"))
  end

  if schema_hsh.key?("maximum")
    solver.assert term.unsigned_le(schema_hsh.fetch("maximum"))
  end

  if schema_hsh.key?("allOf")
    constrain_int(solver, term, schema_hsh.fetch("allOf"))
  end

  if schema_hsh.key?("anyOf")
    raise "TODO"
  end

  if schema_hsh.key?("oneOf")
    raise "TODO"
  end

  if schema_hsh.key?("noneOf")
    raise "TODO"
  end

  if schema_hsh.key?("if")
    raise "TODO"
  end

  if schema_hsh.key?("$ref")
    if schema_hsh.fetch("$ref").split("/").last == "uint32"
      solver.assert((term == 0) | (0 == (term & (term - 1))))
      solver.assert((term.unsigned_gt(0)) & (term.unsigned_le(2**32 - 1)))
    elsif schema_hsh.fetch("$ref").split("/").last == "uint64"
      solver.assert((term == 0) | (0 == (term & (term - 1))))
      solver.assert((term.unsigned_gt(0)) & (term.unsigned_le(2**64 - 1)))
    else
      raise "Unhandled schema $ref: #{schema_hsh.fetch("$ref")}"
    end
  end
end

.constrain_string(solver, term, schema_hsh) ⇒ Object 



140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
# File 'lib/udb/z3.rb', line 140

def self.constrain_string(solver, term, schema_hsh)
  if schema_hsh.key?("const")
    solver.assert(term == schema_hsh.fetch("const").hash)
  end

  if schema_hsh.key?("enum")
    expr = (term == schema_hsh.fetch("enum")[0].hash)
    schema_hsh.fetch("enum")[1..].each do |v|
      expr = expr | (term == v.hash)
    end
    solver.assert expr
  end

  if schema_hsh.key?("anyOf")
    raise "TODO"
  end

  if schema_hsh.key?("oneOf")
    raise "TODO"
  end

  if schema_hsh.key?("noneOf")
    raise "TODO"
  end

  if schema_hsh.key?("if")
    raise "TODO"
  end
end

.detect_array_subtype(schema_hsh) ⇒ Symbol

Parameters:

  • schema_hsh (Hash{String => T.untyped})

Returns:

  • (Symbol) 


318
319
320
321
322
323
324
325
326
 
# File 'lib/udb/z3.rb', line 318

def self.detect_array_subtype(schema_hsh)
  if schema_hsh.key?("items") && schema_hsh.fetch("items").is_a?(Array)
    detect_type(schema_hsh.fetch("items")[0])
  elsif schema_hsh.key?("items")
    detect_type(schema_hsh.fetch("items"))
  else
    raise "Can't detect array subtype"
  end
end

.detect_type(schema_hsh) ⇒ Symbol

Parameters:

  • schema_hsh (Hash{String => T.untyped})

Returns:

  • (Symbol) 


246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
 
# File 'lib/udb/z3.rb', line 246

def self.detect_type(schema_hsh)
  if schema_hsh.key?("type")
    case schema_hsh["type"]
    when "boolean"
      :boolean
    when "integer"
      :int
    when "string"
      :string
    when "array"
      :array
    else
      raise "Unhandled JSON schema type"
    end
  elsif schema_hsh.key?("const")
    case schema_hsh["const"]
    when TrueClass, FalseClass
      :boolean
    when Integer
      :int
    when String
      :string
    else
      raise "Unhandled const type"
    end
  elsif schema_hsh.key?("enum")
    raise "Mixed types in enum" unless schema_hsh["enum"].all? { |e| e.class == schema_hsh["enum"].fetch(0).class }

    case schema_hsh["enum"].fetch(0)
    when TrueClass, FalseClass
      :boolean
    when Integer
      :int
    when String
      :string
    else
      raise "unhandled enum type"
    end
  elsif schema_hsh.key?("allOf")
    subschema_types = schema_hsh.fetch("allOf").map { |subschema| detect_type(subschema) }

    if subschema_types.fetch(0) == :string
      raise "Subschema types do not agree" unless subschema_types[1..].all? { |t| t == :string }

      :string
    elsif subschema_types.fetch(0) == :boolean
      raise "Subschema types do not agree" unless subschema_types[1..].all? { |t| t == :boolean }

      :boolean
    elsif subschema_types.fetch(0) == :int
      raise "Subschema types do not agree" unless subschema_types[1..].all? { |t| t == :int }

      :int
    else
      raise "unhandled subschema type"
    end
  elsif schema_hsh.key?("$ref")
    if schema_hsh.fetch("$ref") == "schema_defs.json#/$defs/uint32"
      :int
    elsif schema_hsh.fetch("$ref") == "schema_defs.json#/$defs/uint64"
      :int
    else
      raise "unhandled ref: #{schema_hsh.fetch("$ref")}"
    end
  elsif schema_hsh.key?("not")
    detect_type(schema_hsh.fetch("not"))
  else
    raise "unhandled scalar schema:\n#{schema_hsh}"
  end
end

Instance Method Details

#!=(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer, String, Boolean)

Returns:

  • (Z3::BoolExpr) 


397
398
399
400
401
402
403
 
# File 'lib/udb/z3.rb', line 397

def !=(val)
  if val.is_a?(String)
    @term != val.hash
  else
    @term != val
  end
end

#<(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer)

Returns:

  • (Z3::BoolExpr) 


411
412
413
 
# File 'lib/udb/z3.rb', line 411

def <(val)
  @term.unsigned_lt(val)
end

#<=(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer)

Returns:

  • (Z3::BoolExpr) 


406
407
408
 
# File 'lib/udb/z3.rb', line 406

def <=(val)
  @term.unsigned_le(val)
end

#==(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer, String, Boolean)

Returns:

  • (Z3::BoolExpr) 


388
389
390
391
392
393
394
 
# File 'lib/udb/z3.rb', line 388

def ==(val)
  if val.is_a?(String)
    @term == val.hash
  else
    @term == val
  end
end

#>(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer)

Returns:

  • (Z3::BoolExpr) 


421
422
423
 
# File 'lib/udb/z3.rb', line 421

def >(val)
  @term.unsigned_gt(val)
end

#>=(val) ⇒ Z3::BoolExpr

Parameters:

  • val (Integer)

Returns:

  • (Z3::BoolExpr) 


416
417
418
 
# File 'lib/udb/z3.rb', line 416

def >=(val)
  @term.unsigned_ge(val)
end

#[](idx) ⇒ Z3::BoolExpr, ...

Parameters:

  • idx (Integer)

Returns:

  • (Z3::BoolExpr, Z3::IntExpr, Z3::BitvecExpr) 


383
384
385
 
# File 'lib/udb/z3.rb', line 383

def [](idx)
  @term[idx]
end

#extract(msb, lsb) ⇒ Z3::BitvecExpr

Parameters:

  • msb (Integer)
  • lsb (Integer)

Returns:

  • (Z3::BitvecExpr) 


378
379
380
 
# File 'lib/udb/z3.rb', line 378

def extract(msb, lsb)
  @term.extract(msb, lsb)
end

#idx_term ⇒ Z3::IntExpr

Returns:

  • (Z3::IntExpr) 


368
369
370
 
# File 'lib/udb/z3.rb', line 368

def idx_term
  @idx_term
end

#max_items ⇒ Integer

Returns:

  • (Integer) 


365
 
# File 'lib/udb/z3.rb', line 365

def max_items = @max_items

#size_term ⇒ Z3::IntExpr

Returns:

  • (Z3::IntExpr) 


373
374
375
 
# File 'lib/udb/z3.rb', line 373

def size_term
  @term.size_term
end