chiark - git - mdw - xyla/blob - t/soak

   1 #! /usr/bin/python3
   2 ###
   3 ### Randomized testing of binary trees
   4 ###
   5 ### (c) 2024 Straylight/Edgeware
   6 ###
   7
   8 ###----- Licensing notice ---------------------------------------------------
   9 ###
  10 ### This file is part of Xyla, a library of binary trees.
  11 ###
  12 ### Xyla is free software: you can redistribute it and/or modify it under
  13 ### the terms of the GNU Lesser General Public License as published by the
  14 ### Free Software Foundation; either version 3 of the License, or (at your
  15 ### option) any later version.
  16 ###
  17 ### Xyla is distributed in the hope that it will be useful, but WITHOUT
  18 ### ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 ### FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20 ### License for more details.
  21 ###
  22 ### You should have received a copy of the GNU Lesser General Public
  23 ### License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24
  25 ###--------------------------------------------------------------------------
  26 ### External dependencies.
  27
  28 import base64 as B64
  29 import errno as E
  30 import io as IO
  31 import math as M
  32 import optparse as OP
  33 import os as OS
  34 import random as RND
  35 import re as RX
  36 import sys as SYS
  37 import subprocess as SUB
  38 import time as T
  39
  40 ###--------------------------------------------------------------------------
  41 ### Preliminaries.
  42
  43 SEEDSZ = 32
  44 B32 = 1 << 32
  45
  46 PROG = OS.path.basename(SYS.argv[0])
  47
  48 def base64_encode(buf):
  49   ## No, you blundering morons, the result of Base64 encoding is text.
  50   return B64.b64encode(buf).decode("us-ascii")
  51
  52 def binsearch(list, key, keyfn, lessfn):
  53   n = len(list)
  54   lo, hi = 0, n
  55   while lo < hi:
  56     mid = (lo + hi)//2
  57     if lessfn(keyfn(list[mid]), key): lo = mid + 1
  58     else: hi = mid
  59   if lo < n and not lessfn(key, keyfn(list[lo])): found = list[lo]
  60   else: found = None
  61   return found, lo
  62
  63 class WeightedChoice (object):
  64   def __init__(me, choices):
  65     me._choices = []
  66     acc = 0
  67     for wt, opt in choices:
  68       acc += wt
  69       me._choices.append((acc - 1, opt))
  70     me._total = acc
  71   def choose(me, rand):
  72     i = rand.randrange(me._total)
  73     ch, j = binsearch(me._choices, i,
  74                       lambda pair: pair[0], lambda x, y: x < y)
  75     return me._choices[j][1]
  76
  77 ###--------------------------------------------------------------------------
  78 ### Super-stupid reference implementation.
  79
  80 class Collection (object):
  81   def __init__(me, items):
  82     me._set = set(items)
  83     me._list = None
  84   def _ensure_list(me):
  85     if me._list is None: me._list = list(me._set); me._list.sort()
  86   def _ensure_set(me):
  87     if me._set is None: me._set = set(me._list)
  88   def __iter__(me):
  89     me._ensure_list(); return iter(me._list)
  90   def __len__(me):
  91     me._ensure_list(); return len(me._list)
  92   def __contains__(me, x):
  93     me._ensure_set(); return x in me._set
  94   def add(me, x):
  95     me._ensure_set(); me._set.add(x); me._list = None
  96   def remove(me, x):
  97     me._ensure_set(); me._set.remove(x); me._list = None
  98   def join(me, x, yy):
  99     me._ensure_list(); yy._ensure_list()
 100     if x is None:
 101       assert not me._list or not yy._list or me._list[-1] < yy._list[0]
 102       mid = []
 103     else:
 104       assert not me._list or me._list[-1] < x;
 105       assert not yy._list or x < yy._list[0]
 106       mid = [x]
 107     return Collection(me._list + mid + yy._list)
 108   def split(me, x):
 109     me._ensure_list()
 110     x, i = binsearch(me._list, x, lambda x: x, lambda x, y: x < y)
 111     if x is None: j = i
 112     else: j = i + 1
 113     return Collection(me._list[:i]), x, Collection(me._list[j:])
 114   def unisect(me, yy):
 115     me._ensure_set(); yy._ensure_set()
 116     return Collection(me._set | yy._set), Collection(me._set&yy._set)
 117   def diffsect(me, yy):
 118     me._ensure_set(); yy._ensure_set()
 119     return Collection(me._set - yy._set), Collection(me._set&yy._set)
 120   def lower(me):
 121     me._ensure_list()
 122     if not me._list: return None
 123     else: return me._list[0]
 124   def upper(me):
 125     me._ensure_list()
 126     if not me._list: return None
 127     else: return me._list[-1]
 128
 129 ###--------------------------------------------------------------------------
 130 ### Options processing.
 131
 132 class Options (object):
 133   def __init__(me):
 134     op = OP.OptionParser\
 135            (usage = "%prog [-c STEPS] [-f FILE] [-l LIMIT] "
 136                     "[-n STEPS] [-s SEED] [-y STEP] PROG [ARGS ...]")
 137     op.disable_interspersed_args()
 138     for short, long, kw in \
 139         [("-c", "--ckpt-steps",
 140           dict(type = "int", metavar = "STEPS",
 141                dest = "ckpt_steps", default = 5000,
 142                help = "number of steps between checkpoints")),
 143          ("-f", "--ckpt-file",
 144           dict(type = "string", metavar = "FILE",
 145                dest = "ckpt_file", default = "soak.ckpt",
 146                help = "file to hold checkpoint information")),
 147          ("-l", "--limit",
 148           dict(type = "int", metavar = "LIMIT",
 149                dest = "limit", default = None,
 150                help = "exclusive limit value to store in test trees")),
 151          ("-n", "--steps",
 152           dict(type = "int", metavar = "STEPS",
 153                dest = "nsteps", default = None,
 154                help = "number of steps to run before stopping")),
 155          ("-s", "--seed",
 156           dict(type = "string", metavar = "SEED",
 157                dest = "seed", default = None,
 158                help = "force initial seed")),
 159          ("-y", "--sync",
 160           dict(type = "int", metavar = "STEP",
 161                dest = "sync", default = None,
 162                help = "check and print state from STEP"))]:
 163       op.add_option(short, long, **kw)
 164     opts, args = op.parse_args()
 165     me.limit = opts.limit
 166     me.ckpt_file = opts.ckpt_file
 167     me.sync = opts.sync
 168     me.ckpt_steps = opts.ckpt_steps
 169     me.nsteps = opts.nsteps
 170     me.seed = opts.seed
 171     if len(args) < 1: op.print_usage(SYS.stderr); SYS.exit(2)
 172     me.testprog = args
 173
 174 ###--------------------------------------------------------------------------
 175 ### Testing state.
 176
 177 class Level (object):
 178   def __init__(me, kind, base, limit, tree = "_"):
 179     xtree, _ = RX.subn(r"0x[0-9a-f]{8}\$", "", tree)
 180     me.coll = Collection(map(int, RX.findall(r"\d+", xtree)))
 181     me.kind, me.base, me.limit, me.tree = \
 182       kind, int(base), int(limit), tree.strip()
 183     me.rlim = int(M.sqrt(me.limit - me.base))
 184   def write(me, file):
 185     file.write("%s %d %d %s\n" % (me.kind, me.base, me.limit, me.tree))
 186   @classmethod
 187   def read(cls, file):
 188     line = file.readline()
 189     if line == "": return None
 190     kind, base, limit, tree = line.split(None, 3)
 191     return cls(kind, base, limit, tree)
 192
 193 class State (object):
 194   def __init__(me, opts):
 195     me._ckpt_file = opts.ckpt_file
 196     try:
 197       with open(me._ckpt_file, "r") as f:
 198         me.seed, = f.readline().split()
 199         stack = []
 200         while True:
 201           lv = Level.read(f)
 202           if lv is None: break
 203           stack.append(lv)
 204       assert stack
 205       me.cur = stack.pop()
 206       me.stack = stack
 207       if opts.seed is not None and me.seed != opts.seed:
 208         raise ValueError("checkpointed seed `%s' /= "
 209                          "command-line seed `%s'" % (me.seed, opts.seed))
 210       if opts.limit is not None and me.cur.limit != opts.limit:
 211         raise ValueError("checkpointed limit %d /= command-line limit %d" %
 212                          (me.cur.limit, opts.limit))
 213     except IOError as err:
 214       if err.errno != E.ENOENT: raise
 215       if opts.seed is not None: me.seed = opts.seed
 216       else: me.seed = base64_encode(OS.urandom(SEEDSZ))
 217       if opts.limit is not None: me.limit = opts.limit
 218       else: me.limit = 4096
 219       me.stack = []
 220       me.cur = Level('base', 0, me.limit)
 221       me.write_ckpt(reseed = False)
 222     me.rand = RND.Random(me.seed)
 223     n, b = 0, me.cur.limit
 224     while True:
 225       bb = int(M.sqrt(b)) + 4
 226       if bb >= b: break
 227       n, b = n + 1, bb
 228     me.stklim = n
 229   def push(me, lv):
 230     me.stack.append(me.cur)
 231     me.cur = lv
 232   def pop(me):
 233     assert me.stack
 234     lv = me.cur
 235     me.cur = me.stack.pop()
 236     return lv
 237   def write_ckpt(me, reseed = True):
 238     if reseed:
 239       me.seed = base64_encode(bytes(me.rand.randrange(256)
 240                                     for _ in range(SEEDSZ)))
 241       me.rand.seed(me.seed)
 242     new = me._ckpt_file + ".new"
 243     with open(new, "w") as f:
 244       f.write("%s\n" % me.seed)
 245       for lv in me.stack: lv.write(f)
 246       me.cur.write(f)
 247     try: OS.rename(new, me._ckpt_file)
 248     except OSError as err:
 249       if err.errno == E.EEXIST:
 250         OS.unlink(me._ckpt_file); OS.rename(new, me._ckpt_file)
 251   def clear_ckpt(me):
 252     try: OS.unlink(me._ckpt_file)
 253     except OSError as err:
 254       if err.errno == E.ENOENT: pass
 255       else: raise
 256
 257 ###--------------------------------------------------------------------------
 258 ### Main machinery.
 259
 260 def choices():
 261   ch = [(896, "addrm1"),
 262         (56, "addrmn"),
 263         (56, "lookup")]
 264
 265   sp = len(ST.stack)
 266   ch += [(ST.stklim - sp, "split"),
 267          (ST.stklim - sp, "push")]
 268
 269   if ST.cur.kind == "join":
 270     ch += [(sp, "join0"), (sp, "join1")]
 271   elif ST.cur.kind == "setop":
 272     ch += [(sp, "unisect"), (sp, "diffsect")]
 273   elif ST.cur.kind == "base":
 274     pass
 275   else:
 276     raise ValueError("unknown level kind `%s'" % ST.cur.kind)
 277
 278   return WeightedChoice(ch)
 279
 280 OPTS = Options()
 281 ST = State(OPTS)
 282 KID = SUB.Popen(OPTS.testprog, universal_newlines = True,
 283                 stdin = SUB.PIPE, stdout = SUB.PIPE)
 284 SYNC = False
 285
 286 def fail(msg):
 287   SYS.stderr.write("%s: FAILED: %s\n" % (PROG, msg))
 288   SYS.stderr.write("%s:   step = %d\n" % (PROG, CSTEP))
 289   KID.stdin.close()
 290   KID.stdout.close()
 291   rc = KID.wait()
 292   SYS.stderr.write("%s:   exit status = %d\n" % (PROG, rc))
 293   SYS.exit(2)
 294
 295 def put(msg, echo = True):
 296   try: KID.stdin.write(msg); KID.stdin.flush()
 297   except IOError as err: fail("write failed: %s" % err)
 298   if SYNC and echo: SYS.stdout.write("$ " + msg); SYS.stdout.flush()
 299 def get(echo = True):
 300   try: line = KID.stdout.readline()
 301   except IOError as err: fail("read failed: %s" % err)
 302   if line == "": fail("unexpected end of file")
 303   if SYNC and echo: SYS.stdout.write(line)
 304   if line[-1] == "\n": return line[:-1]
 305   else: return line
 306
 307 def dump_tree():
 308   if SYNC:
 309     put("D\n:;;END DUMP\n", echo = False)
 310     while True:
 311       line = get(echo = False)
 312       if line == ";;END DUMP": break
 313       SYS.stdout.write(line); SYS.stdout.write("\n")
 314
 315 def check_tree():
 316   put("K\n", echo = False)
 317   line = get(echo = False)
 318   if ST.cur.coll: ref = " ".join("%d" % i for i in ST.cur.coll)
 319   else: ref = "(empty tree)"
 320   if line != ref: fail("iteration mismatch: %s /= %s" % (line, ref))
 321
 322 def snapshot():
 323   put("L\n", echo = False)
 324   ST.cur.tree = get(echo = False)
 325
 326 STEP = CSTEP = 0
 327 for lv in ST.stack:
 328   put("= %s\n" % lv.tree)
 329   dump_tree()
 330   put("(\n")
 331 put("= %s\n" % ST.cur.tree)
 332 dump_tree()
 333 put("S 0x%08x\n" % ST.rand.randrange(B32))
 334
 335 ch = choices()
 336 while OPTS.nsteps is None or STEP < OPTS.nsteps:
 337
 338   if OPTS.sync is not None and OPTS.sync == STEP:
 339     SYNC = True
 340     OPTS.sync = None
 341     snapshot()
 342     SYS.stdout.write("\n;; initial stack\n")
 343     for i, lv in enumerate(ST.stack):
 344       SYS.stdout.write(";; %3d = %s\n" % (i, lv.tree))
 345     SYS.stdout.write(";; TOP = %s\n" % ST.cur.tree)
 346     check_tree()
 347
 348   if SYNC: SYS.stdout.write("\n;; step %d\n" % CSTEP)
 349   op = ch.choose(ST.rand)
 350
 351   if op == "addrm1":
 352     k = ST.rand.randrange(ST.cur.base, ST.cur.limit)
 353     if k in ST.cur.coll: ST.cur.coll.remove(k); put("%d-\n" % k)
 354     else: ST.cur.coll.add(k); put("%d+\n" % k)
 355
 356   elif op == "addrmn":
 357     n = ST.rand.randrange(ST.cur.rlim)
 358     i = ST.rand.randrange(ST.cur.base, ST.cur.limit - n)
 359     m = i + n//2
 360     foundp = m in ST.cur.coll
 361     dir = ST.rand.choice([+1, -1])
 362     rr = range(i, i + n)
 363     if dir < 0: rr = reversed(rr)
 364     firstp = True
 365     buf = IO.StringIO()
 366     if foundp:
 367       for j in rr:
 368         if j not in ST.cur.coll: continue
 369         if firstp: firstp = False
 370         else: buf.write(u" ")
 371         ST.cur.coll.remove(j); buf.write(u"%d-" % j)
 372     else:
 373       for j in rr:
 374         if j in ST.cur.coll: continue
 375         if firstp: firstp = False
 376         else: buf.write(u" ")
 377         ST.cur.coll.add(j); buf.write(u"%d+" % j)
 378     if not firstp: buf.write(u"\n")
 379     put(buf.getvalue())
 380
 381   elif op == "lookup":
 382     k = ST.rand.randrange(ST.cur.base, ST.cur.limit)
 383     put("%d? n\n" % k)
 384     line = get()
 385     if line == "(nil)":
 386       if k in ST.cur.coll: fail("key %d unexpectedly missing" % k)
 387     else:
 388       m = RX.match(r"^#<node #0x[0-9a-f]{8} (\d+)>", line)
 389       if m:
 390         kk = int(m.group(1))
 391         if kk != k: fail("search for key %d found %d instead" % (k, kk))
 392         elif k not in ST.cur.coll: fail("key %d unexpectedly found" % k)
 393       else:
 394         fail("unexpected response to lookup: `%s'" % line)
 395
 396   elif op == "split":
 397     check_tree()
 398     k = ST.rand.randrange(ST.cur.base, ST.cur.limit - ST.cur.rlim - 4)
 399     put("%d@ /\n" % k)
 400     left, mid, right = ST.cur.coll.split(k)
 401     ST.cur.coll = left
 402     old_limit, ST.cur.limit = ST.cur.limit, k
 403     ST.push(Level("split.mid", k, k + 1, str(mid)))
 404     ST.push(Level("split.right", k + 1, old_limit,
 405                   " ".join("%d" % x for x in right)))
 406     dump_tree(); check_tree(); put(")\n"); ST.pop()
 407     dump_tree(); check_tree(); put(")\n"); ST.pop()
 408     dump_tree(); check_tree(); snapshot()
 409     put("(\n")
 410     if ST.cur.coll: new_base = ST.cur.coll.upper() + 2
 411     else: new_base = ST.cur.base + 2
 412     ST.push(Level("join", new_base, old_limit, "_"))
 413     ch = choices()
 414
 415   elif op == "push":
 416     check_tree(); snapshot()
 417     put("(\n"); ST.push(Level("setop", ST.cur.base, ST.cur.limit, "_"))
 418     ST.stack[-1].limit = ST.cur.limit
 419     ch = choices()
 420
 421   elif op == "join0":
 422     lower = ST.stack[-1].coll
 423     put("* ~\n")
 424     ST.stack[-1].coll = lower.join(None, ST.cur.coll)
 425     ST.stack[-1].limit = ST.cur.limit
 426     ST.pop()
 427     ch = choices()
 428
 429   elif op == "join1":
 430     lower = ST.stack[-1].coll
 431     if lower: base = lower.upper() + 1
 432     else: base = ST.stack[-1].base + 1
 433     if ST.cur.coll: limit = ST.cur.coll.lower()
 434     else: limit = ST.cur.limit
 435     k = ST.rand.randrange(base, limit)
 436     put("%d ~\n" % k)
 437     ST.stack[-1].coll = lower.join(k, ST.cur.coll)
 438     ST.stack[-1].limit = ST.cur.limit
 439     ST.pop()
 440     ch = choices()
 441
 442   elif op == "unisect":
 443     put("|\n")
 444     ST.cur.coll, ST.stack[-1].coll = ST.cur.coll.unisect(ST.stack[-1].coll)
 445     dump_tree(); check_tree(); put(")\n"); ST.pop()
 446     ch = choices()
 447
 448   elif op == "diffsect":
 449     put("\\\n")
 450     diff, ST.cur.coll = ST.cur.coll.diffsect(ST.stack[-1].coll)
 451     ST.push(Level("diffsect.diff", ST.cur.base, ST.cur.limit,
 452                   " ".join("%d" % x for x in diff)))
 453     dump_tree(); check_tree(); put(")\n"); ST.pop()
 454     dump_tree(); check_tree(); put(")\n"); ST.pop()
 455     ch = choices()
 456
 457   else:
 458     raise ValueError("unexpected operation `%s'" % op)
 459
 460   STEP += 1; CSTEP += 1
 461   dump_tree()
 462   if SYNC or CSTEP == OPTS.ckpt_steps: check_tree()
 463   if CSTEP == OPTS.ckpt_steps:
 464     snapshot()
 465     ST.write_ckpt()
 466     CSTEP = 0; SYNC = False
 467     put("S 0x%08x\n" % ST.rand.randrange(B32))
 468
 469 while True:
 470   check_tree()
 471   if not ST.stack: break
 472   put(")\n")
 473   ST.pop()
 474   dump_tree()
 475   check_tree()
 476 ST.clear_ckpt()
 477
 478 ###----- That's all, folks --------------------------------------------------