quiver.myr

   1 use std
   2 use math
   3 use regex
   4
   5 use t
   6 use yakmo
   7
   8 pkg quiver =
   9         type vertex = struct
  10                 name : byte[:]
  11
  12                 /* vertex fatness -- usually 1, 2, or 3 */
  13                 d : uint32
  14
  15                 /* For when I get around to writing a Clav-like GUI */
  16                 x_pos : int64
  17                 y_pos : int64
  18                 color : (uint8, uint8, uint8)
  19
  20                 /* TODO: yakmo.polynomial(@a)#, and then genericize everything that follows */
  21                 acoord : std.option(yakmo.polynomial#)
  22                 xcoord : std.option(yakmo.ratfunc#)
  23         ;;
  24         impl disposable vertex
  25         /* TODO: types */
  26         /*
  27         impl t.dupable vertex
  28         */
  29
  30         type quiver = struct
  31                 v : vertex[:]
  32
  33                 /* calculate sigma on the fly */
  34                 epsilon : yakmo.Q#[:][:]
  35
  36                 /* Whether A- and X-coordinates should be used */
  37                 use_a_coords : bool
  38                 use_x_coords : bool
  39         ;;
  40         impl disposable quiver#
  41         impl std.equatable quiver#
  42         impl t.dupable quiver#
  43
  44         type quiver_mk_opts = struct
  45                 use_a_coords : bool
  46                 use_x_coords : bool
  47         ;;
  48
  49         const mk : (-> quiver#)
  50         const mk_with_opts : (opts : quiver_mk_opts -> quiver#)
  51
  52         /*
  53            Can't return the vertex# itself right now... there's some weird typing thing. TODO: bother Ori
  54
  55            Note: dups name, so you can free it.
  56          */
  57         const add_vertex : (q : quiver#, name : byte[:], weight : uint32 -> std.result(std.size, byte[:]))
  58
  59         const delete_vertex : (q : quiver#, name : byte[:] -> std.result(void, byte[:]))
  60
  61         const add_to_edge : (q : quiver#, from_name : byte[:], to_name : byte[:], sigma : yakmo.Q# -> std.result(void, byte[:]))
  62         const mutate_ip : (q : quiver#, vertex_name : byte[:] -> std.result(void, byte[:]))
  63         const mutate_ip_i : (q : quiver#, vertex_index : std.size -> std.result(void, byte[:]))
  64         const mutateseq_ip : (q : quiver#, vertex_names : byte[:][:] -> std.result(void, byte[:]))
  65         const mutateseq_ip_i : (q : quiver#, vertex_indices : std.size[:] -> std.result(void, byte[:]))
  66
  67         /* To get epsilon, just use q.epsilon[from][to] */
  68         const get_sigma : (q : quiver#, from_name : byte[:], to_name : byte[:] -> std.result(yakmo.Q#, byte[:]))
  69         const get_sigma_ii : (q : quiver#, j : std.size, k : std.size -> std.option(yakmo.Q#))
  70
  71         /* Returns (j, &q.v[j]) for unique j s.t. q.v[j].name is name */
  72         const find_vertex : (q : quiver#, name : byte[:] -> std.option((std.size, vertex#)))
  73
  74         /* Serialization */
  75         const from_bytes : (b : byte[:], opts : quiver_mk_opts -> std.result(quiver#, byte[:]))
  76         const to_bytes : (q : quiver# -> byte[:])
  77
  78         /* Equivalences */
  79
  80         /* As graphs: names/weights/edge weights only */
  81         const graph_equivalent : (q1 : quiver.quiver#, q2 : quiver.quiver# -> bool)
  82 ;;
  83
  84
  85 /* TODO: these are already done in libyakmo. Kill 'em once the types detect that. */
  86 impl disposable yakmo.ratfunc# =
  87         __dispose__ = {x : yakmo.ratfunc#
  88                 __dispose__(x.num)
  89                 __dispose__(x.den)
  90                 std.bytefree((x : byte#), sizeof(yakmo.ratfunc))
  91         }
  92 ;;
  93 impl disposable yakmo.polynomial# =
  94         __dispose__ = {p : yakmo.polynomial#
  95                 for var j = 0; j < p.terms.len; ++j
  96                         __dispose__(p.terms[j])
  97                 ;;
  98                 std.slfree(p.terms)
  99                 /* TODO: std.free(p) */
 100                 std.bytefree((p : byte#), sizeof(yakmo.polynomial))
 101         }
 102 ;;
 103 impl disposable yakmo.var_power =
 104         __dispose__ = {vp : yakmo.var_power
 105                 std.slfree(vp.variable)
 106                 __dispose__(vp.power)
 107         }
 108 ;;
 109 impl disposable yakmo.monomial =
 110         __dispose__ = {x : yakmo.monomial
 111                 __dispose__(x.coeff)
 112                 for v : x.vars
 113                         __dispose__(v)
 114                 ;;
 115                 std.slfree(x.vars)
 116         }
 117 ;;
 118 impl disposable yakmo.Q# =
 119         __dispose__ = {q : yakmo.Q#
 120                 std.bigfree(q.p)
 121                 std.bigfree(q.q)
 122                 std.bytefree((q : byte#), sizeof(yakmo.Q))
 123         }
 124 ;;
 125 impl disposable yakmo.Qi# =
 126         __dispose__ = {z : yakmo.Qi#
 127                 __dispose__(z.re)
 128                 __dispose__(z.im)
 129                 std.bytefree((z : byte#), sizeof(yakmo.Qi))
 130         }
 131 ;;
 132 impl disposable yakmo.Z# =
 133         __dispose__ = {a
 134                 var ba : std.bigint# = (a : std.bigint#)
 135                 std.bigfree(ba)
 136         }
 137 ;;
 138
 139 var findnum  : std.result(regex.regex#, regex.status)
 140 var findvert : std.result(regex.regex#, regex.status)
 141 var findedge : std.result(regex.regex#, regex.status)
 142
 143 const __init__ = {
 144         findnum  = regex.compile("^(\\d+) Vertices\n")
 145         findvert = regex.compile("^v[[](\\d+)[]]\\hf:(\\d+)\\hx:(-?\\d+)\\hy:(-?\\d+) c:0x(..)(..)(..) l:(\\d+) n:")
 146         findedge = regex.compile("^e[[](\\d+)[]][[](\\d+)[]] (-?\\d+)/(\\d+)\n")
 147 }
 148
 149 /* TODO: types */
 150 impl disposable vertex =
 151         __dispose__ = {v : vertex
 152                 match v.acoord
 153                 | `std.Some a: __dispose__(a)
 154                 | _:
 155                 ;;
 156                 match v.xcoord
 157                 | `std.Some x: __dispose__(x)
 158                 | _:
 159                 ;;
 160                 std.slfree(v.name)
 161         }
 162 ;;
 163 impl t.dupable vertex =
 164         dup = {v : vertex
 165                 var da
 166                 match v.acoord
 167                 | `std.None: da = `std.None
 168                 | `std.Some a: da = `std.Some t.dup(a)
 169                 ;;
 170
 171                 var dx
 172                 match v.xcoord
 173                 | `std.None: dx = `std.None
 174                 | `std.Some x: dx = `std.Some t.dup(x)
 175                 ;;
 176
 177                 -> [
 178                         .name = std.sldup(v.name),
 179                         .d = v.d,
 180                         .x_pos = v.x_pos,
 181                         .y_pos = v.y_pos,
 182                         .color = v.color,
 183                         .acoord = da,
 184                         .xcoord = dx,
 185                 ]
 186         }
 187 ;;
 188
 189 impl disposable quiver# =
 190         __dispose__ = {q : quiver#
 191                 for vv : q.v
 192                         __dispose__(vv)
 193                 ;;
 194                 std.slfree(q.v)
 195
 196                 for var j = 0; j < q.epsilon.len; ++j
 197                         for var k = 0; k < q.epsilon[j].len; ++k
 198                                 __dispose__(q.epsilon[j][k])
 199                         ;;
 200                         std.slfree(q.epsilon[j])
 201                 ;;
 202                 std.slfree(q.epsilon)
 203                 /* TODO: Types */
 204                 std.bytefree((q : byte#), sizeof(quiver))
 205         }
 206 ;;
 207
 208 /* TODO: types */
 209 impl t.dupable quiver# =
 210         dup = {q : quiver#
 211                 var new_q : quiver = [
 212                         .v = t.dup(q.v),
 213                         .epsilon = t.dup(q.epsilon),
 214                         .use_a_coords = q.use_a_coords,
 215                         .use_x_coords = q.use_x_coords,
 216                 ]
 217                 -> (std.mk(new_q) : quiver#)
 218         }
 219 ;;
 220
 221 impl std.equatable quiver# =
 222         eq = {qa, qb
 223                 if qa.v.len != qb.v.len
 224                         -> false
 225                 ;;
 226
 227                 for var j = 0; j < qa.v.len; ++j
 228                         var v1 : vertex# = &qa.v[j]
 229                         match find_vertex(qb, qa.v[j].name)
 230                         | `std.None: -> false
 231                         | `std.Some (_, v2):
 232                                 /*
 233                                    TODO: split this off into vertex equality.
 234                                    That may screw up types, though.
 235                                  */
 236                                 if !std.eq(v1.name, v2.name)
 237                                         /* impossible */
 238                                         -> false
 239                                 ;;
 240                                 if v1.d != v2.d
 241                                         -> false
 242                                 ;;
 243                                 if v1.x_pos != v2.x_pos
 244                                         -> false
 245                                 ;;
 246                                 if v1.y_pos != v2.y_pos
 247                                         -> false
 248                                 ;;
 249                                 if v1.color.0 != v2.color.0
 250                                         -> false
 251                                 ;;
 252                                 if v1.color.1 != v2.color.1
 253                                         -> false
 254                                 ;;
 255                                 if v1.color.2 != v2.color.2
 256                                         -> false
 257                                 ;;
 258                                 match (v1.acoord, v2.acoord)
 259                                 | (`std.None, `std.None):
 260                                 | (`std.Some _, `std.None): -> false
 261                                 | (`std.None, `std.Some _): -> false
 262                                 | (`std.Some a1, `std.Some a2):
 263                                         if !std.eq(a1, a2)
 264                                                 -> false
 265                                         ;;
 266                                 ;;
 267                                 match (v1.xcoord, v2.xcoord)
 268                                 | (`std.None, `std.None):
 269                                 | (`std.Some _, `std.None): -> false
 270                                 | (`std.None, `std.Some _): -> false
 271                                 | (`std.Some x1, `std.Some x2):
 272                                         if !std.eq(x1, x2)
 273                                                 -> false
 274                                         ;;
 275                                 ;;
 276                         ;;
 277                 ;;
 278
 279                 for var i = 0; i < qa.epsilon.len; ++i
 280                         for var j = 0; j < qa.epsilon.len; ++j
 281                                 if !std.eq(qa.epsilon[i][j], qb.epsilon[i][j])
 282                                         -> false
 283                                 ;;
 284                         ;;
 285                 ;;
 286
 287                 -> true
 288         }
 289 ;;
 290
 291 const mk_with_opts = { opts : quiver_mk_opts
 292         -> std.mk([
 293                 .v = [][:],
 294                 .epsilon = [][:],
 295                 .use_a_coords = opts.use_a_coords,
 296                 .use_x_coords = opts.use_x_coords,
 297         ])
 298 }
 299
 300 const mk = {
 301         -> std.mk([
 302                 .v = [][:],
 303                 .epsilon = [][:],
 304                 .use_a_coords = false,
 305                 .use_x_coords = false,
 306         ])
 307 }
 308
 309 const add_vertex = {q, name, weight
 310         /* No duplicate names allowed */
 311         for vv : q.v
 312                 if std.eq(vv.name, name)
 313                         -> `std.Err std.fmt("vertex \"{}\" already exists in quiver", name)
 314                 ;;
 315         ;;
 316
 317         /* Start out the A-coord and X-coord as trivial */
 318         var v : vertex = [
 319                 .name = std.sldup(name),
 320                 .d = weight,
 321                 .acoord = `std.None,
 322                 .xcoord = `std.None,
 323         ]
 324
 325         /* Add each epsilon(-, v) */
 326         for var j = 0; j < q.v.len; ++j
 327                 std.slpush(&q.epsilon[j], yakmo.gid())
 328         ;;
 329
 330         /* Add each epsilon(v, -) */
 331         var ns : yakmo.Q#[:] = [][:]
 332         for var j = 0; j <= q.v.len; ++j
 333                 std.slpush(&ns, yakmo.gid())
 334         ;;
 335         std.slpush(&q.epsilon, ns)
 336
 337         /* And finally, add v */
 338         std.slpush(&q.v, v)
 339
 340         -> `std.Ok (q.v.len - 1)
 341 }
 342
 343 const delete_vertex = {q, name
 344         /*
 345            TODO: this appears ugly and inefficient -- you're right. This
 346            is to remind me to implement some sort of t.sldispose
 347            function that combines __dispose__ and sldel. With that in
 348            place, this would look much cleaner.
 349          */
 350         var found = false
 351         var j = 0
 352
 353         for j = 0; j < q.v.len; ++j
 354                 if std.eq(q.v[j].name, name)
 355                         found = true
 356                         break
 357                 ;;
 358         ;;
 359
 360         if !found
 361                 -> `std.Err std.fmt("vertex \"{}\" not present", name)
 362         ;;
 363
 364         __dispose__(q.v[j])
 365         std.sldel(&q.v, j)
 366
 367         for var i = 0; i < q.epsilon.len; ++i
 368                 __dispose__(q.epsilon[i][j])
 369                 std.sldel(&q.epsilon[i], j)
 370         ;;
 371
 372         for var i = 0; i < q.epsilon[j].len; ++i
 373                 __dispose__(q.epsilon[j][i])
 374         ;;
 375         std.slfree(q.epsilon[j])
 376         std.sldel(&q.epsilon, j)
 377
 378         -> `std.Ok void
 379 }
 380
 381 const add_to_edge = {q, from_name, to_name, sigma
 382         if std.eq(from_name, to_name)
 383                 -> `std.Err std.fmt("vertices must be different")
 384         ;;
 385
 386         var j : std.size = 0
 387         var k : std.size = 0
 388         var found_j : bool = false
 389         var found_k : bool = false
 390
 391
 392         for var i = 0; i < q.v.len; ++i
 393                 if std.eq(q.v[i].name, from_name)
 394                         found_j = true
 395                         j = i
 396                 ;;
 397
 398                 if std.eq(q.v[i].name, to_name)
 399                         found_k = true
 400                         k = i
 401                 ;;
 402         ;;
 403
 404         if !found_j
 405                 -> `std.Err std.fmt("vertex \"{}\" not present", from_name)
 406         ;;
 407
 408         if !found_k
 409                 -> `std.Err std.fmt("vertex \"{}\" not present", to_name)
 410         ;;
 411
 412         -> add_to_edge_ii(q, j, k, sigma)
 413 }
 414
 415 const add_to_edge_ii = {q, from, to, sigma
 416         if from < 0 || from >= q.v.len || to < 0 || to >= q.v.len
 417                 -> `std.Err std.fmt("indices out of range")
 418         ;;
 419
 420         var weightto = auto yakmo.QfromZ(q.v[to].d)
 421         var weightfrom = auto yakmo.QfromZ(q.v[from].d)
 422         var gcd : yakmo.Q# = auto yakmo.gcd(weightto, weightfrom)
 423         match yakmo.finv(gcd)
 424         | `std.None: -> `std.Err std.fmt("vertex weight gcd ({}, {}) = {} is uninvertible", weightto, weightfrom, gcd)
 425         | `std.Some inv_gcd:
 426                 yakmo.rmul_ip(inv_gcd, sigma)
 427                 yakmo.gadd_ip(q.epsilon[from][to], auto yakmo.rmul(inv_gcd, weightto))
 428                 yakmo.gneg_ip(inv_gcd)
 429                 yakmo.gadd_ip(q.epsilon[to][from], auto yakmo.rmul(inv_gcd, weightfrom))
 430                 auto inv_gcd
 431         ;;
 432
 433         -> `std.Ok void
 434 }
 435
 436 const mutate_ip = {q, vertex_name
 437         var k : std.size = 0
 438         var found_k : bool = false
 439
 440         for var j = 0; j < q.v.len; ++j
 441                 if std.eq(q.v[j].name, vertex_name)
 442                         k = j
 443                         found_k = true
 444                         break
 445                 ;;
 446         ;;
 447
 448         if !found_k
 449                 -> `std.Err std.fmt("vertex “{}” not present", vertex_name)
 450         ;;
 451
 452         -> mutate_ip_i(q, k)
 453 }
 454
 455 const mutate_ip_i = {q, k
 456         if k < 0 || k >= q.v.len
 457                 -> `std.Err std.fmt("index {} out of range", k)
 458         ;;
 459
 460         /* To begin with, get the A-coordinates right */
 461         if q.use_a_coords
 462                 /* TODO: all the __dispose__ littered throughout should become "auto" */
 463                 var coords_plus = yakmo.rid()
 464                 var coords_minus = yakmo.rid()
 465
 466                 var qvka
 467                 match q.v[k].acoord
 468                 | `std.None: -> `std.Err std.fmt("Quiver has A-coordinates enabled, but {} has no A-coordinate set", q.v[k].name)
 469                 | `std.Some a: qvka = a
 470                 ;;
 471
 472                 for var j = 0; j < q.v.len; ++j
 473                         var eps = q.epsilon[k][j]
 474                         var qvja
 475                         match q.v[j].acoord
 476                         | `std.None: -> `std.Err std.fmt("Quiver has A-coordinates enabled, but {} has no A-coordinate set", q.v[j].name)
 477                         | `std.Some a: qvja = a
 478                         ;;
 479                         if eps.p.sign > 0
 480                                 match good_rpowr_poly(qvja, eps)
 481                                 | `std.Ok x:
 482                                         yakmo.rmul_ip(coords_plus, x)
 483                                         __dispose__(x)
 484                                 | `std.Err e:
 485                                         auto (e : t.doomed_str)
 486                                         -> `std.Err std.fmt("good_rpowr_poly({}, {}): {}", qvja, eps, e)
 487                                 ;;
 488                         elif eps.p.sign < 0
 489                                 var neps = yakmo.gneg(eps)
 490                                 match good_rpowr_poly(qvja, neps)
 491                                 | `std.Ok x:
 492                                         yakmo.rmul_ip(coords_minus, x)
 493                                         __dispose__(x)
 494                                 | `std.Err e:
 495                                         auto (e : t.doomed_str)
 496                                         -> `std.Err std.fmt("good_rpowr_poly({}, {}): {}", qvja, neps, e)
 497                                 ;;
 498                                 __dispose__(neps)
 499                         ;;
 500                 ;;
 501
 502                 var sum = auto yakmo.gadd(coords_plus, coords_minus)
 503                 __dispose__(coords_plus)
 504                 __dispose__(coords_minus)
 505
 506                 match yakmo.div_maybe(sum, qvka)
 507                 | `std.None: -> `std.Err std.fmt("Laurent phenomenon fails when mutating at {}: cannot divide {} by {}", q.v[k].name, sum, qvka)
 508                 | `std.Some new_acoord:
 509                         var old_acoord = qvka
 510                         q.v[k].acoord = `std.Some new_acoord
 511                         __dispose__(old_acoord)
 512                 ;;
 513         ;;
 514
 515         /* Now the X-coordinates */
 516         if q.use_x_coords
 517                 var qvkx
 518                 match q.v[k].xcoord
 519                 | `std.None: -> `std.Err std.fmt("Quiver has X-coordinates enabled, but {} has no X-coordinate set", q.v[k].name)
 520                 | `std.Some x: qvkx = x
 521                 ;;
 522
 523                 var xk = t.dup(qvkx)
 524                 var xki
 525                 match yakmo.finv(xk)
 526                 | `std.Some y:
 527                         xki = y
 528                 | `std.None:
 529                         -> `std.Err std.fmt("X-coord of {} is 0", q.v[k].name)
 530                 ;;
 531
 532                 for var j = 0; j < q.v.len; ++j
 533                         if j == k
 534                                 continue
 535                         ;;
 536
 537                         var qvjx
 538                         match q.v[j].xcoord
 539                         | `std.None: -> `std.Err std.fmt("Quiver has X-coordinates enabled, but {} has no X-coordinate set", q.v[j].name)
 540                         | `std.Some x: qvjx = x
 541                         ;;
 542
 543                         var prod = yakmo.rid()
 544                         var exp = yakmo.gneg(q.epsilon[j][k])
 545
 546                         match yakmo.cmp_zero(exp)
 547                         | `std.Equal:
 548                                 __dispose__(exp)
 549                                 __dispose__(prod)
 550                                 continue
 551                         | `std.Before:
 552                                 yakmo.gadd_ip(prod, xki)
 553                                 match yakmo.finv(prod)
 554                                 | `std.Some prodi:
 555                                         __dispose__(prod)
 556                                         prod = prodi
 557                                         yakmo.gneg_ip(exp)
 558                                 | `std.None:
 559                                         -> `std.Err std.fmt("(1 + X^eps) is 0")
 560                                 ;;
 561                         | `std.After:
 562                                 yakmo.gadd_ip(prod, xk)
 563                         ;;
 564
 565                         match good_rpowr_ratfunc(prod, exp)
 566                         | `std.Ok y:
 567                                 yakmo.rmul_ip(qvjx, y)
 568                                 q.v[j].xcoord = `std.Some qvjx
 569                                 __dispose__(y)
 570                         | `std.Err e:
 571                                 auto (e : t.doomed_str)
 572                                 -> `std.Err std.fmt("good_rpowr_ratfunc({}, {}): {}", prod, exp, e)
 573                         ;;
 574
 575                         __dispose__(exp)
 576                         __dispose__(prod)
 577                 ;;
 578
 579                 __dispose__(xk)
 580                 __dispose__(qvkx)
 581                 q.v[k].xcoord = `std.Some xki
 582         ;;
 583
 584         /* Finally, get the quiver right. First, complete all triangles */
 585         for var i = 0; i < q.v.len; ++i
 586                 var eps_ik = q.epsilon[i][k]
 587                 if i == k || yakmo.eqQ(eps_ik, 0, 1)
 588                         continue
 589                 ;;
 590
 591                 for var j = 0; j < q.v.len; ++j
 592                 var eps_kj = q.epsilon[k][j]
 593                         if j == k || j == i || yakmo.eqQ(eps_kj, 0, 1)
 594                                 continue
 595                         ;;
 596
 597                         if eps_ik.p.sign * eps_kj.p.sign <= 0
 598                                 continue
 599                         ;;
 600
 601                         var abs_eps_ik = auto yakmo.abs(eps_ik)
 602                         var summand = auto yakmo.rmul(abs_eps_ik, eps_kj)
 603
 604                         yakmo.gadd_ip(q.epsilon[i][j], summand)
 605                 ;;
 606         ;;
 607
 608         /* Second, flip all incident edges */
 609         for var i = 0; i < q.v.len; ++i
 610                 if i == k
 611                         continue
 612                 ;;
 613                 q.epsilon[k][i].p.sign *= -1
 614                 q.epsilon[i][k].p.sign *= -1
 615         ;;
 616
 617         -> `std.Ok void
 618 }
 619
 620 const mutateseq_ip = {q, vertex_names
 621         for var j = 0; j < vertex_names.len; ++j
 622                 var vertex_name = vertex_names[j]
 623
 624                 match mutate_ip(q, vertex_name)
 625                 | `std.Ok void:
 626                 | `std.Err e:
 627                         auto (e : t.doomed_str)
 628                         -> `std.Err std.fmt("mutate(mu[{}]=\"{}\"): {}", j, vertex_name, e)
 629                 ;;
 630         ;;
 631
 632         -> `std.Ok void
 633 }
 634
 635 const mutateseq_ip_i = {q, vertex_indices
 636         for var j = 0; j < vertex_indices.len; ++j
 637                 match mutate_ip_i(q, vertex_indices[j])
 638                 | `std.Ok void:
 639                 | `std.Err e:
 640                         auto (e : t.doomed_str)
 641                         -> `std.Err std.fmt("mutate(mu[{}]=\"{}\"): {}", j, vertex_indices[j], e)
 642                 ;;
 643         ;;
 644
 645         -> `std.Ok void
 646 }
 647
 648 /* *** This should be in libyakmo (and be generic), but the types are fucking up */
 649
 650 /* and why does only _poly need the explicit labelling in the prototype  ??? */
 651 const good_rpowr_poly : (b : yakmo.polynomial#, exp : yakmo.Q# -> std.result(yakmo.polynomial#, byte[:])) = {b : yakmo.polynomial#, exp : yakmo.Q#
 652         if exp.p.sign < 0
 653                 -> `std.Err std.fmt("{} must be >= 0", exp)
 654         ;;
 655
 656         if !std.bigeqi(exp.q, 1)
 657                 -> `std.Err std.fmt("{} must be an integer", exp)
 658         ;;
 659
 660         var res = yakmo.rid()
 661         var double = t.dup(b)
 662         var np : std.bigint# = std.bigdup(exp.p)
 663         while !std.bigiszero(np)
 664                 if !std.bigiseven(np)
 665                         yakmo.rmul_ip(res, double)
 666                 ;;
 667
 668                 yakmo.rmul_ip(double, double)
 669                 std.bigshri(np, 1)
 670         ;;
 671
 672         __dispose__(double)
 673         std.bigfree(np)
 674         -> `std.Ok res
 675 }
 676 const good_rpowr_ratfunc = {b : yakmo.ratfunc#, exp : yakmo.Q#
 677         if exp.p.sign < 0
 678                 -> `std.Err std.fmt("{} must be >= 0", exp)
 679         ;;
 680
 681         if !std.bigeqi(exp.q, 1)
 682                 -> `std.Err std.fmt("{} must be an integer", exp)
 683         ;;
 684
 685         var res = yakmo.rid()
 686         var double = t.dup(b)
 687         var np : std.bigint# = std.bigdup(exp.p)
 688         while !std.bigiszero(np)
 689                 if !std.bigiseven(np)
 690                         yakmo.rmul_ip(res, double)
 691                 ;;
 692
 693                 yakmo.rmul_ip(double, double)
 694                 std.bigshri(np, 1)
 695         ;;
 696
 697         __dispose__(double)
 698         std.bigfree(np)
 699         -> `std.Ok res
 700 }
 701 /* *** */
 702
 703 const get_sigma = {q, from_name, to_name
 704         var j : std.size = 0
 705         var k : std.size = 0
 706         var found_j : bool = false
 707         var found_k : bool = false
 708
 709
 710         for var i = 0; i < q.v.len; ++i
 711                 if std.eq(q.v[i].name, from_name)
 712                         found_j = true
 713                         j = i
 714                 ;;
 715
 716                 if std.eq(q.v[i].name, to_name)
 717                         found_k = true
 718                         k = i
 719                 ;;
 720         ;;
 721
 722         if !found_j
 723                 -> `std.Err std.fmt("vertex “{}” not present", from_name)
 724         ;;
 725
 726         if !found_k
 727                 -> `std.Err std.fmt("vertex “{}” not present", to_name)
 728         ;;
 729
 730         match get_sigma_ii(q, j, k)
 731         | `std.None: -> `std.Err std.fmt("Malformed vertex weights")
 732         | `std.Some res: -> `std.Ok res
 733         ;;
 734 }
 735
 736 const get_sigma_ii = {q, j, k
 737         if j < 0 || j >= q.v.len || k < 0 || k >= q.v.len
 738                 -> `std.None
 739         ;;
 740         if q.v[j].d <= 0 || q.v[k].d <= 0
 741                 -> `std.None
 742         ;;
 743
 744         var eps = q.epsilon[j][k]
 745
 746         var gcd = 0
 747         var a = q.v[j].d
 748         var b = q.v[k].d
 749         while true
 750                 if b == 0
 751                         gcd = a
 752                         break
 753                 ;;
 754
 755                 var t = a - b*(a / b)
 756                 a = b
 757                 b = t
 758         ;;
 759         var mul = auto std.try(yakmo.Qfrom(gcd, q.v[k].d))
 760         -> `std.Some yakmo.rmul(eps, mul)
 761 }
 762
 763 const find_vertex = {q : quiver#, name : byte[:]
 764         var found : bool = false
 765         var j : std.size = 0
 766         for var k = 0; k < q.v.len; ++k
 767                 if std.eq(name, q.v[k].name)
 768                         if found
 769                                 /* No unique j, return nothing (should be impossible) */
 770                                 -> `std.None
 771                         ;;
 772
 773                         found = true
 774                         j = k
 775                 ;;
 776         ;;
 777
 778         if found
 779                 /* TODO: dummy assignment needed to help types out */
 780                 var v : vertex# = &q.v[j]
 781                 -> `std.Some( (j, v) )
 782         ;;
 783
 784         -> `std.None
 785 }
 786
 787 const from_bytes = {b, opts : quiver_mk_opts
 788         var q : quiver# = mk_with_opts(opts)
 789         var e : byte[:] = [][:]
 790         var res : std.result(quiver#, byte[:]) = `std.Ok q
 791
 792         var numvert : std.size = 0
 793
 794         /* "123 Vertices" */
 795         match findnum
 796         | `std.Err s:
 797                 res = `std.Err std.fmt("can't parse; error compiling findnum regex: {}", s)
 798                 goto done
 799         | `std.Ok r:
 800                 match regex.search(r, b)
 801                 | `std.Some m:
 802                         b = b[m[0].len:]
 803                         numvert = intparsedef(m[1], 0)
 804                 | `std.None:
 805                         res = `std.Err std.fmt("input should start with something like “8 Vertices”")
 806                         goto done
 807                 ;;
 808         ;;
 809
 810         /*  "v[3] f:1 x:401 y:76 c:0x4ce7ff l:2 n:A1" */
 811         match findvert
 812         | `std.Err s:
 813                 res = `std.Err std.fmt("can't parse; error compiling findvert regex: {}", s)
 814                 goto done
 815         | `std.Ok r:
 816                 for var j = 0; j < numvert; ++j
 817                         match regex.search(r, b)
 818                         | `std.Some m:
 819                                 if m.len != 9
 820                                         res = `std.Err std.fmt("malformed [vertex] line {}", j + 2)
 821                                         goto done
 822                                 ;;
 823
 824                                 /*
 825                                    Calculate the name first, so we can
 826                                    advance past it for the next line
 827                                  */
 828                                 var l : std.size = intparsedef(m[8], 0)
 829
 830                                 if b.len - m[0].len < l
 831                                         res = `std.Err std.fmt("malformed [vertex] line {}", j + 2)
 832                                         goto done
 833                                 ;;
 834
 835                                 var name = b[m[0].len:m[0].len + l]
 836                                 b = b[m[0].len + l + 1:]
 837
 838                                 /* Now grab the boring stuff: index, weight, pos, ... */
 839                                 var idx : std.size = intparsedef(m[1], -1)
 840                                 if idx != j
 841                                         res = `std.Err std.fmt("malformed [vertex] line {}; out-of-sequence vertex idx", j + 2)
 842                                         goto done
 843                                 ;;
 844
 845                                 var weight : uint32 = intparsedef(m[2], 0)
 846                                 var x_pos : int64 = intparsedef(m[3], 0)
 847                                 var y_pos : int64 = intparsedef(m[4], 0)
 848                                 var c_r : uint8 = intparsehexdef(m[5], 0)
 849                                 var c_g : uint8 = intparsehexdef(m[6], 0)
 850                                 var c_b : uint8 = intparsehexdef(m[7], 0)
 851                                 match add_vertex(q, name, weight)
 852                                 | `std.Err er:
 853                                         res = `std.Err std.fmt("error for v[{}]: {}", j, er)
 854                                         std.slfree(er)
 855                                         goto done
 856                                 | `std.Ok jj:
 857                                         q.v[jj].x_pos = x_pos
 858                                         q.v[jj].y_pos = y_pos
 859                                         q.v[jj].color = (c_r, c_g, c_b)
 860                                 ;;
 861                         | `std.None:
 862                                 res = `std.Err std.fmt("malformed [vertex] line {}", j + 2)
 863                                 goto done
 864                         ;;
 865                 ;;
 866         ;;
 867         /*  "e[5][4] -1/2" */
 868         match findedge
 869         | `std.Err s:
 870                 res = `std.Err std.fmt("can't parse; error compiling findedge regex: {}", s)
 871                 goto done
 872         | `std.Ok r:
 873                 var ln : std.size = numvert + 2
 874                 while b.len > 0
 875                         match regex.search(r, b)
 876                         | `std.Some m:
 877                                 var j : std.size = intparsedef(m[1], -1)
 878                                 var k : std.size = intparsedef(m[2], -1)
 879                                 var num : int64 = intparsedef(m[3], 0)
 880                                 var den : int64 = intparsedef(m[4], 1)
 881                                 b = b[m[0].len:]
 882
 883                                 if j < 0 || j > q.v.len || k < 0 || k > q.v.len
 884                                         res = `std.Err std.fmt("[edge] line {}: bad indices", ln)
 885                                         goto done
 886                                 ;;
 887
 888                                 /* TODO: types */
 889                                 match yakmo.Qfrom(num, den)
 890                                 | `std.Err er:
 891                                         res = `std.Err std.fmt("[edge] line {}: bad fraction: {}", ln, er)
 892                                         std.slfree(er)
 893                                         goto done
 894                                 | `std.Ok epsilon:
 895                                         __dispose__(q.epsilon[j][k])
 896                                         q.epsilon[j][k] = epsilon
 897                                 ;;
 898                                 ln++
 899                         | `std.None:
 900                                 if std.eq(b, "\n")
 901                                         b = b[1:]
 902                                         ln++
 903                                 else
 904                                         res = `std.Err std.fmt("malformed [edge] line {}: {}", ln, b)
 905                                         goto done
 906                                 ;;
 907                         ;;
 908                 ;;
 909         ;;
 910
 911 :done
 912         match res
 913         | `std.Err _:
 914                 __dispose__(q)
 915         | _ :
 916         ;;
 917
 918         -> res
 919 }
 920
 921 /*
 922    std.intparse with a default value. After all, we matched this stuff
 923    with regex, it's got to be valid, right?
 924  */
 925 generic intparsedef = {s : byte[:], def : @a :: integral,numeric @a
 926         match std.intparse(s)
 927         | `std.Some x: -> x
 928         | `std.None: -> def
 929         ;;
 930 }
 931
 932 generic intparsehexdef = {s : byte[:], def : @a :: integral,numeric @a
 933         match std.intparsebase(s, 16)
 934         | `std.Some x: -> x
 935         | `std.None: -> def
 936         ;;
 937 }
 938
 939 const to_bytes = {q
 940         var sb : std.strbuf# = std.mksb()
 941
 942         std.sbfmt(sb, "{} Vertices\n", q.v.len)
 943
 944         for var j = 0; j < q.v.len; ++j
 945                 var v : vertex# = &q.v[j]
 946                 std.sbfmt(sb, "v[{}] f:{} x:{} y:{} c:0x{w=2,p=0,x}{w=2,p=0,x}{w=2,p=0,x} l:{} n:{}\n",
 947                         j, v.d, v.x_pos, v.y_pos, v.color.0, v.color.1, v.color.2, v.name.len, v.name)
 948         ;;
 949
 950         for var j = 0; j < q.epsilon.len; ++j
 951                 for var k = 0; k < q.epsilon[j].len; ++k
 952                         var e : yakmo.Q# = q.epsilon[j][k]
 953                         if !yakmo.eqQ(e, 0, 1)
 954                                 std.sbfmt(sb, "e[{}][{}] {}/{}\n", j, k, e.p, e.q)
 955                         ;;
 956                 ;;
 957         ;;
 958
 959         -> std.sbfin(sb)
 960 }
 961
 962 /* Whether two quivers are equivalent as graphs. No vertex renaming is permitted */
 963 const graph_equivalent = {q1 : quiver.quiver#, q2 : quiver.quiver#
 964         if q1.v.len != q2.v.len
 965                 -> false
 966         ;;
 967
 968         var perm : std.size[:] = std.slalloc(q1.v.len)
 969         std.slfill(perm, -1)
 970
 971         /*
 972            We're allowed to be sloppy here building the permutation
 973            because no duplicate names are permitted in the quivers.
 974          */
 975         for var j = 0; j < q1.v.len; ++j
 976                 for var k = 0; k < q2.v.len; ++k
 977                         if std.eq(q1.v[j].name, q2.v[k].name)
 978                                 perm[j] = k
 979                                 if q1.v[j].d != q2.v[k].d
 980                                         -> false
 981                                 ;;
 982                                 break
 983                         ;;
 984                 ;;
 985         ;;
 986
 987         for var j = 0; j < q1.v.len; ++j
 988                 for var k = 0; k < q1.v.len; ++k
 989                         if !std.eq(q1.epsilon[j][k], q2.epsilon[perm[j]][perm[k]])
 990                                 -> false
 991                         ;;
 992                 ;;
 993         ;;
 994
 995         -> true
 996 }