philzook58

struct IntDisjointMap
    parents::Vector{Int64}
    values::Vector{Any}
    merge_fun
end

IntDisjointMap(merge_fun) = IntDisjointMap(Vector{Int64}[], [], merge_fun)

Base.length(x::IntDisjointMap) = length(x.parents)

philzook58

(*|
A data structure that I've been more and more interested in recently is the disjoint set datastructure or union-find.
https://en.wikipedia.org/wiki/Disjoint-set_data_structure It's used in egraphs, unification, prolog, and graph connectivity.

I realized a cute representation that is easy to use and prover stuff about, although very inefficient compared to the usual version of disjoint set. It uses a simple functional representation based off the observation that the preimages of a function form disjoint sets. This representation is somewhat analogous to using functions to represent Maps in Coq like in Software Foundations. https://softwarefoundations.cis.upenn.edu/lf-current/Maps.html

The nice thing about this is that it really avoids any termination stickiness. Termination of the `find_root` operation of a union find in an explicit array or tree is not at all obvious and requires side proof or a refined type.
The termination ultimately comes from the fact that you used a finite number of unions to cons

philzook58

import operator
from z3 import *

def lift(z3assert):
    def res(s):
        s.push()
        s.add(z3assert)
        if s.is_good():
            yield
        s.pop()

philzook58

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define FLAG_BUFFER 128
#define MAX_SYM_LEN 4

typedef struct Stonks {
	int shares;

philzook58

(*
ocamlfind ocamlc -package bap -package core_kernel -linkpkg -linkall baptest.ml 
js_of_ocaml +dynlink.js +toplevel.js +zarith_stubs_js/runtime.js +zarith_stubs_js/biginteger.js \
  +base/base_internalhash_types/runtime.js +base/runtime.js +time_now/runtime.js +bin_prot/runtime.js \
  +ppx_expect/collector/runtime.js +base_bigstring/runtime.js +core_kernel/strftime.js +core_kernel/runtime.js \
  +bigstringaf/runtime.js --linkall --extern-fs --toplevel a.out
*)

open Core_kernel
open Bap.Std

philzook58

Build with dune build main.bc.js --release Demonstrates stack overflow on dynlinking the bap_c library.

Troubleshooting is difficult. Unfortunately the overflow error is being caught and translated in a way that obscures the original cause. To find what I believe is an accurate stack trace do the following: Go into _build/default/main.bc.js. Add Error.stackTraceLimit = Infinity; to the top. Grep for RangeError. Add in console.log(e.stack); into the exception handler like so

     {if(e instanceof Array)return e;
      if
       (joo_global_object.RangeError
 &&

philzook58

dune build main.bc.js --release
node _build/default/main.bc.js

Returns

$node _build/default/main.bc.js
/home/philip/Documents/ocaml/bapjs2/jsoo_crash/_build/default/main.bc.js:3937
 {r += exn[1][1];

philzook58

(executable
(name main)
;(modes byte js)
(flags -linkall -g)
; with dune build main.bc.js --release
; gets us to the Sys flushed error.
(js_of_ocaml (flags --toplevel --dynlink +toplevel.js +dynlink.js --disable inline --pretty --source-map-inline
--file /home/philip/.opam/bapjs/lib/bap/bil.plugin
--file /home/philip/.opam/bapjs/lib/bap/primus_lisp.plugin
--file /home/philip/Documents/ocaml/bapjs2/staticload/test.lisp

philzook58

yada yada ayda

/**
     * Returns unionfind parent of Node
     * @param x
     */
    value_type findNode(value_type x) const {
        return sds.findNode(x);
    }

philzook58

Compile the library. I got the various build arguments from souffle-compile. You can also run this in interpreter mode.

../../souffle/build/src/souffle add2.dl -lunionfind -o out -j4
time ./out -j4