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 [-y] [-c STEPS] [-f FILE] [-l LIMIT] "
 101                   "[-n STEPS] 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(action = "store_true", dest = "sync",
 122                help = "check and print state after every step"))]:
 123       op.add_option(short, long, **kw)
 124     opts, args = op.parse_args()
 125     me.limit = opts.limit
 126     me.ckpt_file = opts.ckpt_file
 127     me.sync = opts.sync
 128     me.ckpt_steps = opts.ckpt_steps
 129     me.nsteps = opts.nsteps
 130     if len(args) < 1: op.print_usage(SYS.stderr); SYS.exit(2)
 131     me.testprog = args
 132
 133 class Level (object):
 134   def __init__(me, kind, base, limit, tree = "_"):
 135     me.coll = Collection(map(int, RX.findall(r"\d+", tree)))
 136     me.kind, me.base, me.limit, me.tree = \
 137       kind, int(base), int(limit), tree.strip()
 138     me.rlim = int(M.sqrt(me.limit - me.base))
 139   def write(me, file):
 140     file.write("%s %d %d %s\n" % (me.kind, me.base, me.limit, me.tree))
 141   @classmethod
 142   def read(cls, file):
 143     line = file.readline()
 144     if line == "": return None
 145     kind, base, limit, tree = line.split(maxsplit = 3)
 146     return cls(kind, base, limit, tree)
 147
 148 class State (object):
 149   def __init__(me, opts):
 150     me._ckpt_file = opts.ckpt_file
 151     try:
 152       with open(me._ckpt_file, "r") as f:
 153         me.seed, = f.readline().split()
 154         stack = []
 155         while True:
 156           lv = Level.read(f)
 157           if lv is None: break
 158           stack.append(lv)
 159       assert stack
 160       me.cur = stack.pop()
 161       me.stack = stack
 162       if opts.limit is not None and me.cur.limit != opts.limit:
 163         raise ValueError("checkpointed limit %d /= command-line limit %d" %
 164                          (me.cur.limit, opts.limit))
 165     except OSError as err:
 166       if err.errno != E.ENOENT: raise
 167       me.seed = base64_encode(OS.urandom(SEEDSZ))
 168       if opts.limit is not None: me.limit = opts.limit
 169       else: me.limit = 4096
 170       me.stack = []
 171       me.cur = Level('base', 0, me.limit)
 172       me.write_ckpt(reseed = False)
 173     me.rand = RND.Random(me.seed)
 174     n, b = 0, me.cur.limit
 175     while True:
 176       bb = int(M.sqrt(b)) + 4
 177       if bb >= b: break
 178       n, b = n + 1, bb
 179     me.stklim = n
 180   def push(me, lv):
 181     me.stack.append(me.cur)
 182     me.cur = lv
 183   def pop(me):
 184     assert me.stack
 185     lv = me.cur
 186     me.cur = me.stack.pop()
 187     return lv
 188   def write_ckpt(me, reseed = True):
 189     if reseed:
 190       me.seed = base64_encode(bytes(me.rand.randrange(256)
 191                                     for _ in range(SEEDSZ)))
 192       me.rand.seed(me.seed)
 193     new = me._ckpt_file + ".new"
 194     with open(new, "w") as f:
 195       f.write("%s\n" % me.seed)
 196       for lv in me.stack: lv.write(f)
 197       me.cur.write(f)
 198     OS.rename(new, me._ckpt_file)
 199   def clear_ckpt(me):
 200     try: OS.unlink(me._ckpt_file)
 201     except OSError as err:
 202       if err.errno == E.ENOENT: pass
 203       else: raise
 204
 205 def choices():
 206   ch = [(896, "addrm1"),
 207         (56, "addrmn"),
 208         (56, "lookup")]
 209
 210   sp = len(ST.stack)
 211   ch += [(ST.stklim - sp, "split"),
 212          (ST.stklim - sp, "push")]
 213
 214   if ST.cur.kind == "join":
 215     ch += [(sp, "join0"), (sp, "join1")]
 216   elif ST.cur.kind == "setop":
 217     ch += [(sp, "unisect"), (sp, "diffsect")]
 218   elif ST.cur.kind == "base":
 219     pass
 220   else:
 221     raise ValueError("unknown level kind `%s'" % ST.cur.kind)
 222
 223   return WeightedChoice(ch)
 224
 225 OPTS = Options()
 226 ST = State(OPTS)
 227 KID = SUB.Popen(OPTS.testprog, stdin = SUB.PIPE, stdout = SUB.PIPE)
 228 SYNC = OPTS.sync
 229
 230 def fail(msg):
 231   SYS.stderr.write("%s: FAILED: %s\n" % (PROG, msg))
 232   SYS.stderr.write("%s:   step = %d\n" % (PROG, CSTEP))
 233   KID.stdin.close()
 234   KID.stdout.close()
 235   rc = KID.wait()
 236   SYS.stderr.write("%s:   exit status = %d\n" % (PROG, rc))
 237   SYS.exit(2)
 238
 239 def put(msg, echo = True):
 240   try: KID.stdin.write(msg.encode()); KID.stdin.flush()
 241   except OSError as err: fail("write failed: %s" % err)
 242   if SYNC and echo: SYS.stdout.write("$ " + msg); SYS.stdout.flush()
 243 def get(echo = True):
 244   try: line = KID.stdout.readline().decode()
 245   except OSError as err: fail("read failed: %s" % err)
 246   if line == "": fail("unexpected end of file")
 247   if SYNC and echo: SYS.stdout.write(line)
 248   if line[-1] == "\n": return line[:-1]
 249   else: return line
 250
 251 def dump_tree():
 252   if SYNC:
 253     put("D\n:;;END DUMP\n", echo = False)
 254     while True:
 255       line = get(echo = False)
 256       if line == ";;END DUMP": break
 257       SYS.stdout.write(line); SYS.stdout.write("\n")
 258
 259 def check_tree():
 260   put("i\n", echo = False)
 261   line = get(echo = False)
 262   if ST.cur.coll: ref = " ".join("%d" % i for i in ST.cur.coll)
 263   else: ref = "(empty tree)"
 264   if line != ref: fail("iteration mismatch: %s /= %s" % (line, ref))
 265   put("!:;;END CHECK\n", echo = False)
 266   line = get(echo = False)
 267   if line != ";;END CHECK": fail("unexpected output: `%s'" % line)
 268
 269 def snapshot():
 270   put("L\n", echo = False)
 271   ST.cur.tree = get(echo = False)
 272
 273 for lv in ST.stack:
 274   put("= %s\n" % lv.tree)
 275   dump_tree()
 276   put("(\n")
 277 put("= %s\n" % ST.cur.tree)
 278 dump_tree()
 279
 280 STEP = CSTEP = 0
 281 ch = choices()
 282 while OPTS.nsteps is None or STEP < OPTS.nsteps:
 283   if SYNC: SYS.stdout.write("\n;; step %d\n" % CSTEP)
 284   op = ch.choose(ST.rand)
 285
 286   if op == "addrm1":
 287     k = ST.rand.randrange(ST.cur.base, ST.cur.limit)
 288     if k in ST.cur.coll: ST.cur.coll.remove(k); put("%d-\n" % k)
 289     else: ST.cur.coll.add(k); put("%d+\n" % k)
 290
 291   elif op == "addrmn":
 292     n = ST.rand.randrange(ST.cur.rlim)
 293     i = ST.rand.randrange(ST.cur.base, ST.cur.limit - n)
 294     m = i + n//2
 295     foundp = m in ST.cur.coll
 296     dir = ST.rand.choice([+1, -1])
 297     rr = range(i, i + n)
 298     if dir < 0: rr = reversed(rr)
 299     firstp = True
 300     buf = IO.StringIO()
 301     if foundp:
 302       for j in rr:
 303         if j not in ST.cur.coll: continue
 304         if firstp: firstp = False
 305         else: buf.write(" ")
 306         ST.cur.coll.remove(j); buf.write("%d-" % j)
 307     else:
 308       for j in rr:
 309         if j in ST.cur.coll: continue
 310         if firstp: firstp = False
 311         else: buf.write(" ")
 312         ST.cur.coll.add(j); buf.write("%d+" % j)
 313     if not firstp: buf.write("\n")
 314     put(buf.getvalue())
 315
 316   elif op == "lookup":
 317     k = ST.rand.randrange(ST.cur.base, ST.cur.limit)
 318     put("%d? n\n" % k)
 319     line = get()
 320     if line == "(nil)":
 321       if k in ST.cur.coll: fail("key %d unexpectedly missing" % k)
 322     else:
 323       m = RX.match(r"^#<node #0x[0-9a-f]{8} (\d+)>", line)
 324       if m:
 325         kk = int(m.group(1))
 326         if kk != k: fail("search for key %d found %d instead" % (k, kk))
 327         elif k not in ST.cur.coll: fail("key %d unexpectedly found" % k)
 328       else:
 329         fail("unexpected response to lookup: `%s'" % line)
 330
 331   elif op == "split":
 332     check_tree()
 333     k = ST.rand.randrange(ST.cur.base, ST.cur.limit - ST.cur.rlim - 4)
 334     put("%d@ /\n" % k)
 335     left, mid, right = ST.cur.coll.split(k)
 336     ST.cur.coll = left
 337     old_limit, ST.cur.limit = ST.cur.limit, k
 338     ST.push(Level("split.mid", k, k + 1, str(mid)))
 339     ST.push(Level("split.right", k + 1, old_limit,
 340                   " ".join("%d" % x for x in right)))
 341     dump_tree(); check_tree(); put(")\n"); ST.pop()
 342     dump_tree(); check_tree(); put(")\n"); ST.pop()
 343     dump_tree(); check_tree(); snapshot()
 344     put("(\n")
 345     if ST.cur.coll: new_base = ST.cur.coll.upper() + 2
 346     else: new_base = ST.cur.base + 2
 347     ST.push(Level("join", new_base, old_limit, "_"))
 348     ch = choices()
 349
 350   elif op == "push":
 351     check_tree(); snapshot()
 352     put("(\n"); ST.push(Level("setop", ST.cur.base, ST.cur.limit, "_"))
 353     ST.stack[-1].limit = ST.cur.limit
 354     ch = choices()
 355
 356   elif op == "join0":
 357     lower = ST.stack[-1].coll
 358     put("* ~\n")
 359     ST.stack[-1].coll = lower.join(None, ST.cur.coll)
 360     ST.stack[-1].limit = ST.cur.limit
 361     ST.pop()
 362     ch = choices()
 363
 364   elif op == "join1":
 365     lower = ST.stack[-1].coll
 366     if lower: base = lower.upper() + 1
 367     else: base = ST.stack[-1].base + 1
 368     if ST.cur.coll: limit = ST.cur.coll.lower()
 369     else: limit = ST.cur.limit
 370     k = ST.rand.randrange(base, limit)
 371     put("%d ~\n" % k)
 372     ST.stack[-1].coll = lower.join(k, ST.cur.coll)
 373     ST.stack[-1].limit = ST.cur.limit
 374     ST.pop()
 375     ch = choices()
 376
 377   elif op == "unisect":
 378     put("|\n")
 379     ST.cur.coll, ST.stack[-1].coll = ST.cur.coll.unisect(ST.stack[-1].coll)
 380     dump_tree(); check_tree(); put(")\n"); ST.pop()
 381     ch = choices()
 382
 383   elif op == "diffsect":
 384     put("\\\n")
 385     diff, ST.cur.coll = ST.cur.coll.diffsect(ST.stack[-1].coll)
 386     ST.push(Level("diffsect.diff", ST.cur.base, ST.cur.limit,
 387                   " ".join("%d" % x for x in diff)))
 388     dump_tree(); check_tree(); put(")\n"); ST.pop()
 389     dump_tree(); check_tree(); put(")\n"); ST.pop()
 390     ch = choices()
 391
 392   else:
 393     raise ValueError("unexpected operation `%s'" % op)
 394
 395   STEP += 1; CSTEP += 1
 396   dump_tree()
 397   if SYNC or CSTEP == OPTS.ckpt_steps: check_tree()
 398   if CSTEP == OPTS.ckpt_steps:
 399     snapshot()
 400     ST.write_ckpt()
 401     CSTEP = 0; SYNC = False
 402
 403 while True:
 404   check_tree()
 405   if not ST.stack: break
 406   put(")\n")
 407   ST.pop()
 408   dump_tree()
 409   check_tree()
 410 ST.clear_ckpt()