jury-rig-testing.c

   1 /*
   2  * Copyright (c) 2016, S. Gilles <sgilles@math.umd.edu>
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software
   5  * for any purpose with or without fee is hereby granted, provided
   6  * that the above copyright notice and this permission notice appear
   7  * in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
  10  * WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
  11  * WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
  12  * AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
  13  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
  14  * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  15  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  16  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18 #include <errno.h>
  19 #include <locale.h>
  20 #include <signal.h>
  21 #include <stdint.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include "macros.h"
  27 #include "quiver.h"
  28
  29 /* Upper limit on sequence lengths */
  30 static size_t max_len = 25;
  31
  32 /* Flag for whether to print info */
  33 static volatile sig_atomic_t status_requested = 0;
  34
  35 /* Signal handler */
  36 static void
  37 handle(int sig);
  38
  39 /* Signal handler */
  40 static void handle(int sig)
  41 {
  42         /* XXX: I'd like to check for SIGINFO here */
  43         if (sig == SIGUSR1) {
  44                 status_requested = 1;
  45                 signal(sig, handle);
  46         }
  47 }
  48
  49 /* Make Q_{G_2} U_{02} Q_{G_2} */
  50 static void create_G2(struct quiver *q, size_t *out_num_nonfrozen,
  51                       size_t **target_mutation, size_t *target_mutation_num)
  52 {
  53         if (!q) {
  54                 return;
  55         }
  56
  57         size_t v0, vinf, v1, v2, v3, v4, v1b, v2b, v3b, v4b, v12, v21, v32, v23,
  58                v30, v03, v10, v01;
  59
  60         /* Q_{G_2} U_{02} Q_{G_2} */
  61         quiver_add_vertex(q, &v0, "0", 1, -13, 143, 0);
  62         quiver_add_vertex(q, &vinf, "\u221e", 3, 8, -125, 0);
  63         quiver_add_vertex(q, &v1, "1", 3, 121, -128, 0);
  64         quiver_add_vertex(q, &v2, "2", 1, 306, -4, 0);
  65         quiver_add_vertex(q, &v3, "3", 3, 192, 15, 0);
  66         quiver_add_vertex(q, &v4, "4", 1, 255, -133, 0);
  67         quiver_add_vertex(q, &v1b, "1*", 3, -122, 7, 0);
  68         quiver_add_vertex(q, &v2b, "2*", 1, -108, -129, 0);
  69         quiver_add_vertex(q, &v3b, "3*", 3, -219, -5, 0);
  70         quiver_add_vertex(q, &v4b, "4*", 1, -195, -182, 0);
  71         *out_num_nonfrozen = v4b + 1;
  72         quiver_add_vertex(q, &v12, "12", 3, -381, -260, 0);
  73         quiver_add_vertex(q, &v21, "21", 1, -226, -384, 0);
  74         quiver_add_vertex(q, &v32, "32", 1, 390, -230, 0);
  75         quiver_add_vertex(q, &v23, "23", 3, 241, -393, 0);
  76         quiver_add_vertex(q, &v30, "30", 3, 379, 131, 0);
  77         quiver_add_vertex(q, &v03, "03", 1, 238, 371, 0);
  78         quiver_add_vertex(q, &v10, "10", 1, -370, 229, 0);
  79         quiver_add_vertex(q, &v01, "01", 3, -182, 353, 0);
  80
  81         /* edges */
  82         quiver_add_to_edge(q, v0, v1b, 1, 1, 0);
  83         quiver_add_to_edge(q, v10, v01, 1, 2, 0);
  84         quiver_add_to_edge(q, v12, v21, 1, 2, 0);
  85         quiver_add_to_edge(q, v23, v32, 1, 2, 0);
  86         quiver_add_to_edge(q, v30, v03, 1, 2, 0);
  87         quiver_add_to_edge(q, v1b, vinf, 1, 1, 0);
  88         quiver_add_to_edge(q, v1b, v2b, 1, 1, 0);
  89         quiver_add_to_edge(q, v2b, v3b, 1, 1, 0);
  90         quiver_add_to_edge(q, v2b, v0, 1, 1, 0);
  91         quiver_add_to_edge(q, v3b, v1b, 1, 1, 0);
  92         quiver_add_to_edge(q, v3b, v4b, 1, 1, 0);
  93         quiver_add_to_edge(q, v4b, v2b, 1, 1, 0);
  94         quiver_add_to_edge(q, v4b, v10, 1, 1, 0);
  95         quiver_add_to_edge(q, v4b, v12, 1, 1, 0);
  96         quiver_add_to_edge(q, v0, v32, 1, 1, 0);
  97         quiver_add_to_edge(q, v1, v2, 1, 1, 0);
  98         quiver_add_to_edge(q, vinf, v1, 1, 1, 0);
  99         quiver_add_to_edge(q, v3, v1, 1, 1, 0);
 100         quiver_add_to_edge(q, v1, v30, 1, 1, 0);
 101         quiver_add_to_edge(q, v2, v3, 1, 1, 0);
 102         quiver_add_to_edge(q, v2, v03, 1, 1, 0);
 103         quiver_add_to_edge(q, v3, v4, 1, 1, 0);
 104         quiver_add_to_edge(q, v4, v2, 1, 1, 0);
 105         quiver_add_to_edge(q, v4, v0, 1, 1, 0);
 106         quiver_add_to_edge(q, v4, v23, 1, 1, 0);
 107         quiver_add_to_edge(q, vinf, v01, 1, 1, 0);
 108         quiver_add_to_edge(q, v01, v1b, 1, 1, 0);
 109         quiver_add_to_edge(q, v10, v21, 1, 1, 0);
 110         quiver_add_to_edge(q, v12, v3b, 1, 1, 0);
 111         quiver_add_to_edge(q, v21, v4b, 1, 1, 0);
 112         quiver_add_to_edge(q, v23, v3, 1, 1, 0);
 113         quiver_add_to_edge(q, v32, v4, 1, 1, 0);
 114         quiver_add_to_edge(q, v30, vinf, 1, 1, 0);
 115         quiver_add_to_edge(q, v03, v1, 1, 1, 0);
 116         quiver_set_warning_threshold(q, 4, 0);
 117         size_t mutation[] = { v0, vinf, v3, v2, v1, v3, v4, v2, v1b, v2b, v4b,
 118                               v0, v3, v1, v4, v3b, v1b, v2b, v0, v3, v3b, v2b,
 119                               v1b, v3b };
 120
 121         *target_mutation_num = (sizeof(mutation)) / (sizeof(mutation[0]));
 122         *target_mutation = malloc(sizeof(*target_mutation) *
 123                                   (*target_mutation_num));
 124
 125         for (size_t k = 0; k < *target_mutation_num; ++k) {
 126                 (*target_mutation)[k] = mutation[k];
 127         }
 128 }
 129
 130 static void create_C2(struct quiver *q, size_t *out_num_nonfrozen,
 131                       size_t **target_mutation, size_t *target_mutation_num)
 132 {
 133         if (!q) {
 134                 return;
 135         }
 136
 137         size_t v0, vinf, v1, v2, v1b, v2b, v12, v21, v23, v32, v30, v03, v10,
 138                v01;
 139
 140         /* Q_{C_2} U_{02} Q_{C_2} */
 141         quiver_add_vertex(q, &v0, "0", 1, 0, -170, 0);
 142         quiver_add_vertex(q, &vinf, "\u221e", 2, 0, 170, 0);
 143         quiver_add_vertex(q, &v1, "1", 2, 100, 100, 0);
 144         quiver_add_vertex(q, &v2, "2", 1, 170, -70, 0);
 145         quiver_add_vertex(q, &v1b, "1*", 2, -140, 100, 0);
 146         quiver_add_vertex(q, &v2b, "2*", 1, -140, -70, 0);
 147         *out_num_nonfrozen = v2b + 1;
 148         quiver_add_vertex(q, &v12, "12", 2, -350, -150, 0);
 149         quiver_add_vertex(q, &v21, "21", 1, -150, -350, 0);
 150         quiver_add_vertex(q, &v32, "32", 1, 350, -150, 0);
 151         quiver_add_vertex(q, &v23, "23", 2, 150, -350, 0);
 152         quiver_add_vertex(q, &v30, "30", 2, 350, 150, 0);
 153         quiver_add_vertex(q, &v03, "03", 1, 150, 350, 0);
 154         quiver_add_vertex(q, &v10, "10", 1, -350, 150, 0);
 155         quiver_add_vertex(q, &v01, "01", 2, -150, 350, 0);
 156
 157         /* edges */
 158         quiver_add_to_edge(q, v12, v21, 1, 2, 0);
 159         quiver_add_to_edge(q, v23, v32, 1, 2, 0);
 160         quiver_add_to_edge(q, v10, v01, 1, 2, 0);
 161         quiver_add_to_edge(q, v30, v03, 1, 2, 0);
 162         quiver_add_to_edge(q, v01, v1b, 1, 1, 0);
 163         quiver_add_to_edge(q, v03, v1, 1, 1, 0);
 164         quiver_add_to_edge(q, v0, v1b, 1, 1, 0);
 165         quiver_add_to_edge(q, v0, v32, 1, 1, 0);
 166         quiver_add_to_edge(q, v10, v21, 1, 1, 0);
 167         quiver_add_to_edge(q, v12, v1b, 1, 1, 0);
 168         quiver_add_to_edge(q, v1b, v2b, 1, 1, 0);
 169         quiver_add_to_edge(q, v1b, vinf, 1, 1, 0);
 170         quiver_add_to_edge(q, v1, v2, 1, 1, 0);
 171         quiver_add_to_edge(q, v1, v30, 1, 1, 0);
 172         quiver_add_to_edge(q, v21, v2b, 1, 1, 0);
 173         quiver_add_to_edge(q, v23, v1, 1, 1, 0);
 174         quiver_add_to_edge(q, v2b, v0, 1, 1, 0);
 175         quiver_add_to_edge(q, v2b, v10, 1, 1, 0);
 176         quiver_add_to_edge(q, v2b, v12, 1, 1, 0);
 177         quiver_add_to_edge(q, v2, v0, 1, 1, 0);
 178         quiver_add_to_edge(q, v2, v03, 1, 1, 0);
 179         quiver_add_to_edge(q, v2, v23, 1, 1, 0);
 180         quiver_add_to_edge(q, v30, vinf, 1, 1, 0);
 181         quiver_add_to_edge(q, v32, v2, 1, 1, 0);
 182         quiver_add_to_edge(q, vinf, v01, 1, 1, 0);
 183         quiver_add_to_edge(q, vinf, v1, 1, 1, 0);
 184         quiver_set_warning_threshold(q, 3, 0);
 185         size_t mutation[] = { v0, vinf, v1, v2, v1b, v2b, v0, v1, v1b };
 186
 187         *target_mutation_num = (sizeof(mutation)) / (sizeof(mutation[0]));
 188         *target_mutation = malloc(sizeof(*target_mutation) *
 189                                   (*target_mutation_num));
 190
 191         for (size_t k = 0; k < *target_mutation_num; ++k) {
 192                 (*target_mutation)[k] = mutation[k];
 193         }
 194 }
 195
 196 /* Main loop */
 197 int main(int argc, char **argv)
 198 {
 199         int ret = 0;
 200         struct quiver q = { 0 };
 201
 202         setlocale(LC_ALL, "");
 203         size_t num_nonfrozen = 0;
 204         size_t *target_mutation = 0;
 205         size_t target_mutation_num = 0;
 206
 207         if (argc != 2 &&
 208             argc != 3) {
 209                 printf("Argument should be either \"C2\" or \"G2\"\n");
 210
 211                 return 1;
 212         }
 213
 214         if (!strcmp(argv[1], "C2")) {
 215                 create_C2(&q, &num_nonfrozen, &target_mutation,
 216                           &target_mutation_num);
 217         } else if (!strcmp(argv[1], "G2")) {
 218                 create_G2(&q, &num_nonfrozen, &target_mutation,
 219                           &target_mutation_num);
 220         } else {
 221                 printf("Argument should be either \"C2\" or \"G2\"\n");
 222
 223                 return 1;
 224         }
 225
 226         size_t startlen = 0;
 227
 228         if (argc == 3) {
 229                 startlen = strtoll(argv[2], 0, 10);
 230         }
 231
 232         /* Set up target edges */
 233         for (size_t j = 0; j < target_mutation_num; ++j) {
 234                 quiver_mutate(&q, target_mutation[j], 0, 0);
 235         }
 236
 237         struct rational *target = 0;
 238
 239         if (!(target = malloc(sizeof *target * q.v_num * q.v_num))) {
 240                 ret = errno;
 241                 perror(L("malloc"));
 242                 goto done;
 243         }
 244
 245         for (size_t i = 0; i < q.v_num * q.v_num; ++i) {
 246                 target[i] = (struct rational) { .p = 0, .q = 1 };
 247         }
 248
 249         for (size_t i = 0; i < q.v_num; ++i) {
 250                 for (size_t j = 0; j < q.v_num; ++j) {
 251                         target[i * q.v_num + j] = q.e[i * q.v_len + j];
 252                 }
 253         }
 254
 255         /* Undo mutations */
 256         for (size_t j = target_mutation_num; j > 0; --j) {
 257                 quiver_mutate(&q, target_mutation[j - 1], 0, 0);
 258         }
 259
 260         /* Now, the long haul*/
 261         size_t len = num_nonfrozen;
 262
 263         if (startlen) {
 264                 len = startlen - 1;
 265         }
 266
 267         signal(SIGUSR1, handle);
 268         size_t s = 0;
 269         size_t c_idx;
 270         int warn = 0;
 271         uint_fast8_t correct = 0;
 272
 273         while (len < max_len) {
 274                 len++;
 275                 size_t sequence[len];
 276
 277                 for (size_t k = 0; k < len; ++k) {
 278                         /* This will get pruned, it's okay */
 279                         sequence[k] = 0;
 280                 }
 281
 282                 c_idx = 0;
 283 have_full_sequence:
 284
 285                 if (status_requested) {
 286                         status_requested = 0;
 287                         printf("%s: Quiver type %s, current sequence %s",
 288                                argv[0], argv[1], q.v[sequence[0]].name);
 289
 290                         for (size_t k = 1; k < len; ++k) {
 291                                 printf(", %s", q.v[sequence[k]].name);
 292                         }
 293
 294                         printf("\n");
 295                         fflush(stdout);
 296                 }
 297
 298                 /*
 299                  * Here, we have computed a full sequence that we want
 300                  * to check.  c_idx is in [0, len - 1], and the quiver
 301                  * has been mutated following the sequence up to (but
 302                  * not including) c_idx.
 303                  *
 304                  * This code is duplicated from increment_sequence
 305                  * because it is reasonable to start the whole process
 306                  * with a sequence that may, in fact, produce warnings.
 307                  */
 308                 warn = 0;
 309
 310                 while (c_idx < len) {
 311                         /* Prune duplicates (involutions) */
 312                         if (c_idx &&
 313                             sequence[c_idx] == sequence[c_idx - 1]) {
 314                                 goto increment_sequence;
 315                         }
 316
 317                         /* Proceed one more mutation */
 318                         quiver_mutate(&q, sequence[c_idx], &warn, 0);
 319
 320                         if (warn) {
 321                                 /* That mutation caused a warning: skip it */
 322                                 quiver_mutate(&q, sequence[c_idx], &warn, 0);
 323
 324                                 /* And try the sequence, starting at c_idx */
 325                                 goto increment_sequence;
 326                         }
 327
 328                         /*
 329                          * Skip ... X, Y ... when X > Y and the edge
 330                          * from X to Y is trivial
 331                          */
 332                         if (c_idx &&
 333                             sequence[c_idx] < sequence[c_idx - 1]) {
 334                                 size_t x = sequence[c_idx - 1];
 335                                 size_t y = sequence[c_idx];
 336                                 struct rational *xy = &(q.e[x * q.v_len + y]);
 337                                 struct rational *yx = &(q.e[y * q.v_len + x]);
 338
 339                                 if (!xy->p &&
 340                                     !yx->p) {
 341                                         /* Undo mutation */
 342                                         quiver_mutate(&q, sequence[c_idx], 0,
 343                                                       0);
 344
 345                                         /* And try the sequence, starting at c_idx */
 346                                         goto increment_sequence;
 347                                 }
 348                         }
 349
 350                         c_idx++;
 351                 }
 352
 353                 /*
 354                  * Here, there's a full sequence, and the quiver has
 355                  * been mutated according to it (all of it).  We want
 356                  * to check if the result matches the target.
 357                  */
 358                 correct = 1;
 359
 360                 for (size_t i = 0; i < q.v_num; ++i) {
 361                         for (size_t j = 0; j < q.v_num; ++j) {
 362                                 struct rational *e = &(q.e[i * q.v_len + j]);
 363                                 struct rational *f = &(target[i * q.v_num + j]);
 364
 365                                 if (e->p * f->q != f->p * e->q) {
 366                                         correct = 0;
 367                                         i = q.v_num + 1;
 368                                         j = i;
 369                                 }
 370                         }
 371                 }
 372
 373                 if (correct) {
 374                         printf("SEQUENCE:     %s", q.v[sequence[0]].name);
 375
 376                         for (size_t k = 1; k < len; ++k) {
 377                                 printf(", %s", q.v[sequence[k]].name);
 378                         }
 379
 380                         printf("\n");
 381                         fflush(stdout);
 382                 }
 383
 384                 c_idx = len - 1;
 385                 quiver_mutate(&q, sequence[c_idx], 0, 0);
 386 increment_sequence:
 387
 388                 /*
 389                  * Here, we have some kind of sequence. The quiver agrees
 390                  * with it up to (but not including) c_idx, and we want
 391                  * to increment it at c_idx.
 392                  */
 393                 s++;
 394                 sequence[c_idx]++;
 395
 396                 if (c_idx == 2) {
 397                         double completed = sequence[0] * num_nonfrozen *
 398                                            num_nonfrozen + sequence[1] *
 399                                            num_nonfrozen +
 400                                            sequence[2] - 1;
 401                         double total = num_nonfrozen * num_nonfrozen *
 402                                        num_nonfrozen;
 403
 404                         printf("Length %zu: completed %.3g%%\n", len, (100.0 *
 405                                                                        completed)
 406                                / total);
 407                         fflush(stdout);
 408                 }
 409
 410                 /* Skip over repeats: each mutation is an involution */
 411                 if (c_idx > 0 &&
 412                     sequence[c_idx] == sequence[c_idx - 1]) {
 413                         sequence[c_idx]++;
 414                 }
 415
 416                 /* Wrap back to 0 */
 417                 if (sequence[c_idx] >= num_nonfrozen) {
 418                         if (!c_idx) {
 419                                 goto exhausted_len;
 420                         }
 421
 422                         c_idx--;
 423                         quiver_mutate(&q, sequence[c_idx], 0, 0);
 424                         goto increment_sequence;
 425                 }
 426
 427                 if (c_idx != len - 1) {
 428                         /*
 429                          * Here, we now have a start of a sequence.
 430                          * The quiver agrees with our start up to (but
 431                          * not including) c_idx, and we want to possibly
 432                          * complete this to a full sequence. First,
 433                          * however, we need to make sure that we don't
 434                          * introduce any warnings at c_idx.
 435                          *
 436                          * This single-mutation testing block could be
 437                          * ignored, but I have a vague suspicion it will
 438                          * be a hot path.
 439                          */
 440                         warn = 0;
 441                         quiver_mutate(&q, sequence[c_idx], &warn, 0);
 442
 443                         if (warn) {
 444                                 /* That mutation caused a warning: skip it */
 445                                 quiver_mutate(&q, sequence[c_idx], &warn, 0);
 446
 447                                 /* And try the sequence, starting at c_idx */
 448                                 goto increment_sequence;
 449                         }
 450
 451                         /*
 452                          * Quivers almost commute: in particular if
 453                          * the edge v_i -> v_j is zero, then mutation
 454                          * at v_i and v_j commute. So if we're at X, Y
 455                          * in the list, and X > Y, then we've actually
 456                          * already computed that branch of the tree,
 457                          * back when it was Y, X. Therefore, increment X.
 458                          */
 459                         if (c_idx &&
 460                             sequence[c_idx] < sequence[c_idx - 1]) {
 461                                 size_t x = sequence[c_idx - 1];
 462                                 size_t y = sequence[c_idx];
 463                                 struct rational *xy = &(q.e[x * q.v_len + y]);
 464                                 struct rational *yx = &(q.e[y * q.v_len + x]);
 465
 466                                 if (!xy->p &&
 467                                     !yx->p) {
 468                                         /* Undo mutation */
 469                                         quiver_mutate(&q, sequence[c_idx], 0,
 470                                                       0);
 471
 472                                         /* And try the sequence, starting at c_idx */
 473                                         goto increment_sequence;
 474                                 }
 475                         }
 476
 477                         /*
 478                          * Here the quiver agrees with our start up
 479                          * to and including c_idx, and we need to fill
 480                          * it out into a full sequence so that it can
 481                          * be tested.  We don't need to perform all the
 482                          * mutations of that full sequence, but we do
 483                          * need to generate the minimal one.
 484                          */
 485                         for (size_t i = c_idx + 1; i < len; ++i) {
 486                                 sequence[i] = 1 - !!((i - c_idx) % 2);
 487                         }
 488
 489                         c_idx++;
 490                 }
 491
 492                 goto have_full_sequence;
 493 exhausted_len:
 494
 495                 /*
 496                  * Here, we have c_idx = 0, and the quiver has not been
 497                  * mutated by anything in sequence
 498                  */
 499                 printf("Exhausted length %zu\n", len);
 500         }
 501
 502         fflush(stdout);
 503 done:
 504         free(target);
 505
 506         return ret;
 507 }