Bundler outputs sorting function that hangs in an infinite loop

Question

Bundler outputs sorting function that hangs in an infinite loop

mikesol opened this issue 2 years ago · 3 comments

It looks like something about the List.sortBy code-gen'd function hangs in an infinite loop. I've copied the relevant code below. I edited the list by hand to make the repro more minimal - I'm pretty sure it's what the codegen would have output, but I'm not sure.

My preliminary analysis indicates that sequedesceascen doesn't get called with enough arguments, so mergeAll doesn't work.

The compiler's JS backend doesn't have this issue and seems to call descending and ascending with the correct number of arguments.

Let me know if I can help solve this!

const data = {"tag":"Cons","_1":{"version":{"tag":"Version","_1":0},"name":{"tag":"Just","_1":"intro 1"},"marker4Time":3.140395482159665,"marker4AudioURL":{"tag":"Nothing"},"marker3Time":2.350910584410028,"marker3AudioURL":{"tag":"Nothing"},"marker2Time":1.649146230854796,"marker2AudioURL":{"tag":"Nothing"},"marker1Time":0.947381,"marker1AudioURL":{"tag":"Nothing"},"column":7},"_2":{"tag":"Nil"}}

var ordNumberImpl = function (lt) {
    return function (eq) {
      return function (gt) {
        return function (x) {
          return function (y) {
            return x < y ? lt : x === y ? eq : gt;
          };
        };
      };
    };
  };
const $Ordering = tag => ({tag});
const LT = /* #__PURE__ */ $Ordering("LT");
const GT = /* #__PURE__ */ $Ordering("GT");
const EQ = /* #__PURE__ */ $Ordering("EQ");
const $List = (tag, _1, _2) => ({tag, _1, _2});
const Nil = /* #__PURE__ */ $List("Nil");
const Cons = value0 => value1 => $List("Cons", value0, value1);
const ordNumber = {compare: /* #__PURE__ */ ordNumberImpl(LT)(EQ)(GT), Eq0: () => eqNumber};
sortingFunction = x => y => ordNumber.compare(x.marker1Time)(y.marker1Time)
const sortBy = cmp => {
    const merge = v => v1 => {
      if (v.tag === "Cons") {
        if (v1.tag === "Cons") {
          if (cmp(v._1)(v1._1).tag === "GT") { return $List("Cons", v1._1, merge(v)(v1._2)); }
          return $List("Cons", v._1, merge(v._2)(v1));
        }
        if (v1.tag === "Nil") { return v; }
        fail();
      }
      if (v.tag === "Nil") { return v1; }
      if (v1.tag === "Nil") { return v; }
      fail();
    };
    const mergePairs = v => {
      if (v.tag === "Cons") {
        if (v._2.tag === "Cons") { return $List("Cons", merge(v._1)(v._2._1), mergePairs(v._2._2)); }
        return v;
      }
      return v;
    };
    const mergeAll = mergeAll$a0$copy => {
      let mergeAll$a0 = mergeAll$a0$copy, mergeAll$c = true, mergeAll$r;
      while (mergeAll$c) {
        const v = mergeAll$a0;
        if (v.tag === "Cons") {
          if (v._2.tag === "Nil") {
            mergeAll$c = false;
            mergeAll$r = v._1;
            continue;
          }
          mergeAll$a0 = mergePairs(v);
          continue;
        }
        mergeAll$a0 = mergePairs(v);
        continue;
      };
      return mergeAll$r;
    };
    const sequedesceascen = sequedesceascen$b$copy => sequedesceascen$a0$copy => sequedesceascen$a1$copy => sequedesceascen$a2$copy => sequedesceascen$a3$copy => {
      let sequedesceascen$b = sequedesceascen$b$copy;
      let sequedesceascen$a0 = sequedesceascen$a0$copy;
      let sequedesceascen$a1 = sequedesceascen$a1$copy;
      let sequedesceascen$a2 = sequedesceascen$a2$copy;
      let sequedesceascen$a3 = sequedesceascen$a3$copy;
      let sequedesceascen$c = true;
      let sequedesceascen$r;
      while (sequedesceascen$c) {
        if (sequedesceascen$b === 0) {
          const v = sequedesceascen$a0;
          if (v.tag === "Cons") {
            if (v._2.tag === "Cons") {
              if (cmp(v._1)(v._2._1).tag === "GT") {
                sequedesceascen$b = 1;
                sequedesceascen$a0 = v._2._1;
                sequedesceascen$a1 = $List("Cons", v._1, Nil);
                sequedesceascen$a2 = v._2._2;
                continue;
              }
              sequedesceascen$b = 2;
              sequedesceascen$a0 = v._2._1;
              sequedesceascen$a1 = v1 => $List("Cons", v._1, v1);
              sequedesceascen$a2 = v._2._2;
              continue;
            }
            sequedesceascen$c = false;
            sequedesceascen$r = $List("Cons", v, Nil);
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", v, Nil);
          continue;
        }
        if (sequedesceascen$b === 1) {
          const a = sequedesceascen$a0, as = sequedesceascen$a1, v = sequedesceascen$a2;
          if (v.tag === "Cons") {
            if (cmp(a)(v._1).tag === "GT") {
              sequedesceascen$b = 1;
              sequedesceascen$a0 = v._1;
              sequedesceascen$a1 = $List("Cons", a, as);
              sequedesceascen$a2 = v._2;
              continue;
            }
            sequedesceascen$c = false;
            sequedesceascen$r = $List("Cons", $List("Cons", a, as), sequences(v));
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", $List("Cons", a, as), sequences(v));
          continue;
        }
        if (sequedesceascen$b === 2) {
          const a = sequedesceascen$a0, as = sequedesceascen$a1, v = sequedesceascen$a2;
          if (v.tag === "Cons") {
            if (
              (() => {
                const $8 = cmp(a)(v._1);
                return $8.tag === "LT" || !($8.tag === "GT");
              })()
            ) {
              sequedesceascen$b = 2;
              sequedesceascen$a0 = v._1;
              sequedesceascen$a1 = ys => as($List("Cons", a, ys));
              sequedesceascen$a2 = v._2;
              continue;
            }
            sequedesceascen$c = false;
            sequedesceascen$r = $List("Cons", as($List("Cons", a, Nil)), sequences(v));
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", as($List("Cons", a, Nil)), sequences(v));
          continue;
        }
      };
      return sequedesceascen$r;
    };
    const sequences = /* #__PURE__ */ sequedesceascen(0);
    const descending = /* #__PURE__ */ sequedesceascen(1);
    const ascending = /* #__PURE__ */ sequedesceascen(2);
    return x => mergeAll(sequences(x));
  };
  sortBy(sortingFunction)(data);

Answer 1 · 2022-08-26T15:52:50.000Z

Had time after work to put together a cleaner, self-contained example that triggers the bug.

Input:

module Main where

import Prelude

import Data.List (sortBy, (:), List(..))
import Effect (Effect)
import Effect.Console (log)

main :: Effect Unit
main = do
  let a = sortBy compare (1 : 2 : 42 : 41 : Nil)
  log $ show a

Bundled ourtput:

// output-es/runtime.js
function fail() {
  throw new Error("Failed pattern match");
}

// output-es/Data.Show/foreign.js
var showIntImpl = function(n) {
  return n.toString();
};

// output-es/Data.Show/index.js
var showInt = { show: showIntImpl };

// output-es/Data.Ordering/index.js
var $Ordering = (tag) => ({ tag });
var LT = /* @__PURE__ */ $Ordering("LT");
var GT = /* @__PURE__ */ $Ordering("GT");
var EQ = /* @__PURE__ */ $Ordering("EQ");

// output-es/Data.List.Types/index.js
var $List = (tag, _1, _2) => ({ tag, _1, _2 });
var Nil = /* @__PURE__ */ $List("Nil");
var listMap = (f) => {
  const chunkedRevMap = (chunkedRevMap$a0$copy) => (chunkedRevMap$a1$copy) => {
    let chunkedRevMap$a0 = chunkedRevMap$a0$copy, chunkedRevMap$a1 = chunkedRevMap$a1$copy, chunkedRevMap$c = true, chunkedRevMap$r;
    while (chunkedRevMap$c) {
      const chunksAcc = chunkedRevMap$a0, v = chunkedRevMap$a1;
      const $4 = (chunksAcc1, xs) => {
        const reverseUnrolledMap = (reverseUnrolledMap$a0$copy) => (reverseUnrolledMap$a1$copy) => {
          let reverseUnrolledMap$a0 = reverseUnrolledMap$a0$copy, reverseUnrolledMap$a1 = reverseUnrolledMap$a1$copy, reverseUnrolledMap$c = true, reverseUnrolledMap$r;
          while (reverseUnrolledMap$c) {
            const v1 = reverseUnrolledMap$a0, acc = reverseUnrolledMap$a1;
            if (v1.tag === "Cons") {
              if (v1._1.tag === "Cons") {
                if (v1._1._2.tag === "Cons") {
                  if (v1._1._2._2.tag === "Cons") {
                    reverseUnrolledMap$a0 = v1._2;
                    reverseUnrolledMap$a1 = $List("Cons", f(v1._1._1), $List("Cons", f(v1._1._2._1), $List("Cons", f(v1._1._2._2._1), acc)));
                    continue;
                  }
                  reverseUnrolledMap$c = false;
                  reverseUnrolledMap$r = acc;
                  continue;
                }
                reverseUnrolledMap$c = false;
                reverseUnrolledMap$r = acc;
                continue;
              }
              reverseUnrolledMap$c = false;
              reverseUnrolledMap$r = acc;
              continue;
            }
            reverseUnrolledMap$c = false;
            reverseUnrolledMap$r = acc;
            continue;
          }
          ;
          return reverseUnrolledMap$r;
        };
        return reverseUnrolledMap(chunksAcc1)((() => {
          if (xs.tag === "Cons") {
            if (xs._2.tag === "Cons") {
              if (xs._2._2.tag === "Nil") {
                return $List("Cons", f(xs._1), $List("Cons", f(xs._2._1), Nil));
              }
              return Nil;
            }
            if (xs._2.tag === "Nil") {
              return $List("Cons", f(xs._1), Nil);
            }
            return Nil;
          }
          return Nil;
        })());
      };
      if (v.tag === "Cons") {
        if (v._2.tag === "Cons") {
          if (v._2._2.tag === "Cons") {
            chunkedRevMap$a0 = $List("Cons", v, chunksAcc);
            chunkedRevMap$a1 = v._2._2._2;
            continue;
          }
          chunkedRevMap$c = false;
          chunkedRevMap$r = $4(chunksAcc, v);
          continue;
        }
        chunkedRevMap$c = false;
        chunkedRevMap$r = $4(chunksAcc, v);
        continue;
      }
      chunkedRevMap$c = false;
      chunkedRevMap$r = $4(chunksAcc, v);
      continue;
    }
    ;
    return chunkedRevMap$r;
  };
  return chunkedRevMap(Nil);
};
var showList = (dictShow) => ({
  show: (v) => {
    if (v.tag === "Nil") {
      return "Nil";
    }
    const go = (go$a0$copy) => (go$a1$copy) => {
      let go$a0 = go$a0$copy, go$a1 = go$a1$copy, go$c = true, go$r;
      while (go$c) {
        const b = go$a0, v$1 = go$a1;
        if (v$1.tag === "Nil") {
          go$c = false;
          go$r = b;
          continue;
        }
        if (v$1.tag === "Cons") {
          go$a0 = (() => {
            if (b.init) {
              return { init: false, acc: v$1._1 };
            }
            return { init: false, acc: b.acc + (" : " + v$1._1) };
          })();
          go$a1 = v$1._2;
          continue;
        }
        fail();
      }
      ;
      return go$r;
    };
    return "(" + (go({ init: true, acc: "" })(listMap(dictShow.show)(v)).acc + " : Nil)");
  }
});

// output-es/Data.List/index.js
var sortBy = (cmp) => {
  const merge = (v) => (v1) => {
    if (v.tag === "Cons") {
      if (v1.tag === "Cons") {
        if (cmp(v._1)(v1._1).tag === "GT") {
          return $List("Cons", v1._1, merge(v)(v1._2));
        }
        return $List("Cons", v._1, merge(v._2)(v1));
      }
      if (v1.tag === "Nil") {
        return v;
      }
      fail();
    }
    if (v.tag === "Nil") {
      return v1;
    }
    if (v1.tag === "Nil") {
      return v;
    }
    fail();
  };
  const mergePairs = (v) => {
    if (v.tag === "Cons") {
      if (v._2.tag === "Cons") {
        return $List("Cons", merge(v._1)(v._2._1), mergePairs(v._2._2));
      }
      return v;
    }
    return v;
  };
  const mergeAll = (mergeAll$a0$copy) => {
    let mergeAll$a0 = mergeAll$a0$copy, mergeAll$c = true, mergeAll$r;
    while (mergeAll$c) {
      const v = mergeAll$a0;
      if (v.tag === "Cons") {
        if (v._2.tag === "Nil") {
          mergeAll$c = false;
          mergeAll$r = v._1;
          continue;
        }
        mergeAll$a0 = mergePairs(v);
        continue;
      }
      mergeAll$a0 = mergePairs(v);
      continue;
    }
    ;
    return mergeAll$r;
  };
  const sequedesceascen = (sequedesceascen$b$copy) => (sequedesceascen$a0$copy) => (sequedesceascen$a1$copy) => (sequedesceascen$a2$copy) => (sequedesceascen$a3$copy) => {
    let sequedesceascen$b = sequedesceascen$b$copy;
    let sequedesceascen$a0 = sequedesceascen$a0$copy;
    let sequedesceascen$a1 = sequedesceascen$a1$copy;
    let sequedesceascen$a2 = sequedesceascen$a2$copy;
    let sequedesceascen$a3 = sequedesceascen$a3$copy;
    let sequedesceascen$c = true;
    let sequedesceascen$r;
    while (sequedesceascen$c) {
      if (sequedesceascen$b === 0) {
        const v = sequedesceascen$a0;
        if (v.tag === "Cons") {
          if (v._2.tag === "Cons") {
            if (cmp(v._1)(v._2._1).tag === "GT") {
              sequedesceascen$b = 1;
              sequedesceascen$a0 = v._2._1;
              sequedesceascen$a1 = $List("Cons", v._1, Nil);
              sequedesceascen$a2 = v._2._2;
              continue;
            }
            sequedesceascen$b = 2;
            sequedesceascen$a0 = v._2._1;
            sequedesceascen$a1 = (v1) => $List("Cons", v._1, v1);
            sequedesceascen$a2 = v._2._2;
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", v, Nil);
          continue;
        }
        sequedesceascen$c = false;
        sequedesceascen$r = $List("Cons", v, Nil);
        continue;
      }
      if (sequedesceascen$b === 1) {
        const a = sequedesceascen$a0, as = sequedesceascen$a1, v = sequedesceascen$a2;
        if (v.tag === "Cons") {
          if (cmp(a)(v._1).tag === "GT") {
            sequedesceascen$b = 1;
            sequedesceascen$a0 = v._1;
            sequedesceascen$a1 = $List("Cons", a, as);
            sequedesceascen$a2 = v._2;
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", $List("Cons", a, as), sequences(v));
          continue;
        }
        sequedesceascen$c = false;
        sequedesceascen$r = $List("Cons", $List("Cons", a, as), sequences(v));
        continue;
      }
      if (sequedesceascen$b === 2) {
        const a = sequedesceascen$a0, as = sequedesceascen$a1, v = sequedesceascen$a2;
        if (v.tag === "Cons") {
          if ((() => {
            const $8 = cmp(a)(v._1);
            return $8.tag === "LT" || !($8.tag === "GT");
          })()) {
            sequedesceascen$b = 2;
            sequedesceascen$a0 = v._1;
            sequedesceascen$a1 = (ys) => as($List("Cons", a, ys));
            sequedesceascen$a2 = v._2;
            continue;
          }
          sequedesceascen$c = false;
          sequedesceascen$r = $List("Cons", as($List("Cons", a, Nil)), sequences(v));
          continue;
        }
        sequedesceascen$c = false;
        sequedesceascen$r = $List("Cons", as($List("Cons", a, Nil)), sequences(v));
        continue;
      }
    }
    ;
    return sequedesceascen$r;
  };
  const sequences = /* @__PURE__ */ sequedesceascen(0);
  const descending = /* @__PURE__ */ sequedesceascen(1);
  const ascending = /* @__PURE__ */ sequedesceascen(2);
  return (x) => mergeAll(sequences(x));
};

// output-es/Data.Eq/foreign.js
var refEq = function(r1) {
  return function(r2) {
    return r1 === r2;
  };
};
var eqIntImpl = refEq;

// output-es/Data.Eq/index.js
var eqInt = { eq: eqIntImpl };

// output-es/Data.Ord/foreign.js
var unsafeCompareImpl = function(lt) {
  return function(eq) {
    return function(gt) {
      return function(x) {
        return function(y) {
          return x < y ? lt : x === y ? eq : gt;
        };
      };
    };
  };
};
var ordIntImpl = unsafeCompareImpl;

// output-es/Data.Ord/index.js
var ordInt = { compare: /* @__PURE__ */ ordIntImpl(LT)(EQ)(GT), Eq0: () => eqInt };

// output-es/Effect.Console/foreign.js
var log = function(s) {
  return function() {
    console.log(s);
  };
};

// output-es/Main/index.js
var main = /* @__PURE__ */ (() => log(showList(showInt).show(sortBy(ordInt.compare)($List(
  "Cons",
  1,
  $List("Cons", 2, $List("Cons", 42, $List("Cons", 41, Nil)))
)))))();

// index.mjs
main();

Answer 2 · 2022-08-26T16:17:28.000Z

Ah, yeah, we need to pad the definitions:

  const sequences = /* @__PURE__ */ sequedesceascen(0);
  const descending = /* @__PURE__ */ sequedesceascen(1);
  const ascending = /* @__PURE__ */ sequedesceascen(2);

sequedesceascen needs to be called with a uniform number of arguments, and this isn't uniform!

Answer 3 · 2022-08-26T17:55:42.000Z

Happy to try a quick fix if you can concoct one!