name = "algebraic-graphs"
description = "Algebraic graphs library (snowleopard/alga). Bug fixes mined from upstream history; modern HEAD is the base, each patch reverse-applies a fix to install the original bug."
language = "haskell"
strategies = ["quickcheck", "hedgehog", "falsify", "smallcheck"]
crate = "algebraic-graphs"
base_commit = "d4e43fb42db05413459fb2df493361d5a666588a"

# ---------------------------------------------------------------------------
# Variant: de_bruijn_dim_zero_8e1591a1_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["de_bruijn_dim_zero_8e1591a1_1"]

[tasks.source]
repo = "https://github.com/snowleopard/alga"
commits = ["8e1591a1d4ad435f766dac4672da66d733816293"]
commit_subjects = ["Fix deBruijn graphs"]
origin = "internal"
summary = "deBruijn 0 used to return `vertex []` (a graph with one vertex, no edges). The fix returns `edge [] []` (the self-loop on the empty word), restoring the family invariant `edgeCount (deBruijn n xs) == (length (nub xs))^(n+1)` at n=0 — at n=0 this is 1, matching one self-loop."

[tasks.injection]
kind = "patch"
files = ["src/Algebra/Graph.hs"]
locations = [{ file = "src/Algebra/Graph.hs", line = 1032, symbol = "deBruijn" }]
patch = "patches/de_bruijn_dim_zero_8e1591a1_1.patch"

[tasks.bug]
short_name = "debruijn_zero_no_self_loop"
invariant = "deBruijn 0 alphabet returns the De Bruijn graph of dimension 0, namely a single self-loop on the empty word. AdjacencyMap.edgeList of (deBruijn 0 xs) must equal [([], [])] for every alphabet xs (including [])."
how_triggered = "Reverse-applying the patch swaps `edge [] []` for `vertex []` at src/Algebra/Graph.hs:1032. The graph then has 0 edges, so edgeList = []."

[[tasks.tasks]]
property = "DeBruijnZeroSelfLoop"
witnesses = [
  { test_fn = "witness_de_bruijn_zero_self_loop_case_alphabet_two",  note = "deBruijn 0 [1,2] must equal edge [] []" },
  { test_fn = "witness_de_bruijn_zero_self_loop_case_empty_alphabet", note = "deBruijn 0 [] must equal edge [] []" },
]

# ---------------------------------------------------------------------------
# Variant: show_no_parens_f2a9683f_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["show_no_parens_f2a9683f_1"]

[tasks.source]
repo = "https://github.com/snowleopard/alga"
commits = ["f2a9683f1c22a7e82715ac4dbb37052e12078e26"]
commit_subjects = ["Fix Show instances to insert parens (#142)"]
origin = "internal"
summary = "The Show instance for AdjacencyMap (and Relation, AdjacencyIntMap, etc.) defined `show` directly with `++`. This left `showsPrec p` at the default `\\_ x s -> show x ++ s`, so any context that called `showsPrec p g` with `p > 10` (e.g. inside `Just g`) skipped the surrounding parens, producing unparseable output like `\"Just edge 1 2\"` instead of `\"Just (edge 1 2)\"`. The fix switches to `showsPrec` + `showParen (p > 10)`."

[tasks.injection]
kind = "patch"
files = ["src/Algebra/Graph/AdjacencyMap.hs"]
locations = [{ file = "src/Algebra/Graph/AdjacencyMap.hs", line = 176, symbol = "Show AdjacencyMap" }]
patch = "patches/show_no_parens_f2a9683f_1.patch"

[tasks.bug]
short_name = "show_adjmap_missing_parens"
invariant = "For any non-empty AdjacencyMap g (whose `show g` is more than the atomic token `\"empty\"`), `show (Just g)` must equal `\"Just (\" ++ show g ++ \")\"`. This is what `showsPrec` at prec 11 buys you; `show g` alone never lies, but the surrounding context's `showsPrec` does."
how_triggered = "Reverse-applying the patch swaps the `showsPrec p ... = showParen (p > 10) $ ...` instance for the old `show ... = \"...\"` instance. Default `showsPrec` then ignores the precedence and prints `Just edge 1 2` without parens."

[[tasks.tasks]]
property = "ShowWithParens"
witnesses = [
  { test_fn = "witness_show_with_parens_case_two_vertices", note = "show (Just (vertices [1,2])) must equal \"Just (vertices [1,2])\"" },
  { test_fn = "witness_show_with_parens_case_single_edge",  note = "show (Just (edges [(1,2)])) must equal \"Just (edge 1 2)\"" },
]

# ---------------------------------------------------------------------------
# Variant: minimum_mempty_pure_e0aa4bee_1
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["minimum_mempty_pure_e0aa4bee_1"]

[tasks.source]
repo = "https://github.com/snowleopard/alga"
commits = ["e0aa4beec88d1c1fa746603d4af8b6061e643886"]
commit_subjects = ["Fix various instances in Algebra.Graph.Label and add tests (#232)"]
origin = "internal"
summary = "The Monoid instance for Minimum had `mempty = pure mempty` (i.e. Finite of the inner monoid's identity, which is the SMALLEST value, not the largest). Combined with `(<>) = liftA2 min`, the left-identity law `mempty <> x == x` failed: `pure (Sum 0) <> pure (Sum 5) = pure (Sum 0)`. The fix sets `mempty = noMinimum` (Infinite, the absorbing element of `min`) and `(<>) = min`."

[tasks.injection]
kind = "patch"
files = ["src/Algebra/Graph/Label.hs"]
locations = [{ file = "src/Algebra/Graph/Label.hs", line = 325, symbol = "Monoid (Minimum a)" }]
patch = "patches/minimum_mempty_pure_e0aa4bee_1.patch"

[tasks.bug]
short_name = "minimum_monoid_identity_violated"
invariant = "Minimum's Monoid satisfies the left-identity law: `mempty <> x == x` for every x. Concretely, `mempty <> pure (Sum n) == pure (Sum n)` for every n > 0."
how_triggered = "Reverse-applying the patch reinstates `mempty = pure mempty` and `(<>) = liftA2 min`. For any positive n, `mempty <> pure (Sum n) = liftA2 min (pure (Sum 0)) (pure (Sum n)) = pure (Sum 0)`, which is not equal to `pure (Sum n)`."

[[tasks.tasks]]
property = "MinimumMonoidIdentity"
witnesses = [
  { test_fn = "witness_minimum_monoid_identity_case_five",  note = "mempty <> pure (Sum 5) must equal pure (Sum 5)" },
  { test_fn = "witness_minimum_monoid_identity_case_seven", note = "mempty <> pure (Sum 7) must equal pure (Sum 7)" },
]

# ---------------------------------------------------------------------------
# Variant: extended_zero_times_infinity_e0aa4bee_2
# ---------------------------------------------------------------------------
[[tasks]]
mutations = ["extended_zero_times_infinity_e0aa4bee_2"]

[tasks.source]
repo = "https://github.com/snowleopard/alga"
commits = ["e0aa4beec88d1c1fa746603d4af8b6061e643886"]
commit_subjects = ["Fix various instances in Algebra.Graph.Label and add tests (#232)"]
origin = "internal"
summary = "Extended's Num instance had `(*) = liftM2 (*)`. By Extended's Monad, `Finite 0 * Infinite = Finite 0 >>= \\_ -> Infinite >>= ... = Infinite`, violating the semiring annihilator law `0 * x == 0`. The fix special-cases `Finite 0 * _ = Finite 0` and `_ * Finite 0 = Finite 0` before falling back to `liftM2 (*)`."

[tasks.injection]
kind = "patch"
files = ["src/Algebra/Graph/Label.hs"]
locations = [{ file = "src/Algebra/Graph/Label.hs", line = 284, symbol = "Num (Extended a)" }]
patch = "patches/extended_zero_times_infinity_e0aa4bee_2.patch"

[tasks.bug]
short_name = "extended_zero_times_infinity"
invariant = "Extended's Num instance satisfies the semiring annihilator law: `Finite 0 * Infinite == Finite 0` and `Infinite * Finite 0 == Finite 0`."
how_triggered = "Reverse-applying the patch removes the `Finite 0 * _` and `_ * Finite 0` pattern matches, leaving `(*) = liftM2 (*)`. The Monad on Extended makes `Finite 0 * Infinite` equal `Infinite`, not `Finite 0`."

[[tasks.tasks]]
property = "ExtendedZeroTimesInfinity"
witnesses = [
  { test_fn = "witness_extended_zero_times_infinity_case_zero", note = "Finite 0 * Infinite == Finite 0 and Infinite * Finite 0 == Finite 0" },
]
