chiark - git - mdw - xyla/blob - soak

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