FAILURE MAP
← Case archive

FA-97256 / Recipe scaling and nutrition / Open access

Sub-recipe allergen roll-up: error propagation · case 01

A missing sub-recipe is silently ignored and a partial allergen list is published.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Errors returned from sub-recipe visits are discarded.

VERIFIED REPAIR

Return the first sub-recipe error immediately.

Unsuccessful approach: Propagating only cycles still hides unknown sub-recipes.

Case contract

recipes maps name -> {allergens, may_contain, uses}. Walk root and every used sub-recipe (depth first, in order). Names canonicalize: trim, lower, synonyms dairy->milk, peanuts->peanut, tree nuts->tree nut, eggs->egg. Result {contains, may_contain (minus contains), error: None}, both sorted. A shared sub-recipe reached twice (diamond) is fine; a cycle returns error "cycle: name" and an unknown name "unknown: name", with empty lists, stopping at the first error.

Why this case matters

Menu allergen matrices must propagate through nested sub-recipes without false cycle errors.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(recipes, root):
    SYN = {'dairy': 'milk', 'peanuts': 'peanut', 'tree nuts': 'tree nut', 'eggs': 'egg'}
    def canon(a):
        a = a.strip().lower()
        return SYN.get(a, a)
    contains, may = set(), set()
    state = {}
    def visit(n):
        if n not in recipes:
            return 'unknown: ' + n
        if state.get(n) == 1:
            return 'cycle: ' + n
        if state.get(n) == 2:
            return None
        state[n] = 1
        r = recipes[n]
        contains.update(canon(a) for a in r.get('allergens', []))
        may.update(canon(a) for a in r.get('may_contain', []))
        for s in r.get('uses', []):
            e = visit(s)
            if e:
                pass
        state[n] = 2
        return None
    err = visit(root)
    if err:
        return {'contains': [], 'may_contain': [], 'error': err}
    return {'contains': sorted(contains), 'may_contain': sorted(may - contains), 'error': None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce']},
     'crust': {'allergens': [], 'may_contain': ['eggs'], 'uses': ['filling', 'topping', 'sauce']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame '],
               'may_contain': ['tree nuts', 'wheat'],
               'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'cycle: sauce', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['soy'], 'may_contain': ['wheat', 'milk'], 'uses': ['topping', 'mystery']},
     'crust': {'allergens': ['dairy', 'peanuts'], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['sauce']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust']},
     'topping': {'allergens': ['milk'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['dairy'], 'may_contain': [], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['tree nuts'], 'may_contain': ['milk'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['peanuts', 'soy'], 'may_contain': [' sesame '], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['peanuts', 'wheat'], 'uses': ['crust', 'filling']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['dairy', 'milk'], 'uses': ['filling']},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': []},
     'topping': {'allergens': [], 'may_contain': ['peanuts', 'milk'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['sauce', 'filling', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['peanuts', 'eggs'], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'topping': {'allergens': ['milk', 'tree nuts'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}]],
 [['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': ['Egg'], 'may_contain': ['soy'], 'uses': ['crust', 'filling', 'mystery']},
     'crust': {'allergens': ['milk'], 'may_contain': ['milk'], 'uses': []},
     'filling': {'allergens': ['eggs', 'milk'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['sauce', 'mystery']},
     'crust': {'allergens': ['eggs'], 'may_contain': ['soy'], 'uses': ['topping', 'base']},
     'filling': {'allergens': ['soy', 'wheat'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['dairy', 'tree nuts'], 'uses': ['filling']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['wheat', 'milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'crust': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping']},
     'filling': {'allergens': ['milk', 'dairy'], 'may_contain': ['tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'base', 'mystery']},
     'topping': {'allergens': ['Egg', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'peanut'], 'error': None, 'may_contain': ['tree nut']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['eggs', 'soy'], 'uses': ['crust']},
     'crust': {'allergens': [], 'may_contain': ['dairy', 'eggs'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame ', 'tree nuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['wheat'], 'may_contain': [' sesame ', 'tree nuts'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': None, 'may_contain': ['egg', 'milk', 'sesame', 'soy', 'tree nut']}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['soy', 'eggs'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'filling': {'allergens': [' sesame ', 'Egg'], 'may_contain': ['eggs', 'peanuts'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'sesame'], 'error': None, 'may_contain': ['peanut', 'soy']}]],
 [['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['regression: error propagation',
   [{'base': {'allergens': ['milk'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['eggs'], 'may_contain': [' sesame ', 'dairy'], 'uses': []},
     'filling': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'tree nuts'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': ['Egg', 'eggs'], 'may_contain': ['dairy'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['mystery']},
     'filling': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['topping', 'base']},
     'sauce': {'allergens': [], 'may_contain': ['peanuts', 'eggs'], 'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['eggs', 'peanuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['soy'],
              'may_contain': ['dairy', 'wheat'],
              'uses': ['sauce', 'filling', 'topping']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['Egg', 'dairy'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['dairy', 'soy'], 'uses': []},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['Egg'], 'uses': ['crust']},
     'topping': {'allergens': ['soy', 'milk'], 'may_contain': ['tree nuts', 'soy'], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['tree nut', 'wheat']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy'], 'may_contain': ['soy', 'wheat'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'milk'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg', 'tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': ['soy'],
               'may_contain': ['wheat', ' sesame '],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['sesame', 'tree nut', 'wheat']}],
  ['generated control 3',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'crust': {'allergens': ['milk', 'eggs'], 'may_contain': ['wheat'], 'uses': []},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat', 'soy'], 'may_contain': ['eggs', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': []}]],
 [['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [' sesame '], 'may_contain': ['soy', 'wheat'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping', 'mystery']},
     'sauce': {'allergens': [], 'may_contain': [' sesame ', 'soy'], 'uses': []},
     'topping': {'allergens': ['eggs'], 'may_contain': [], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: filling', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['eggs', 'peanuts'], 'may_contain': [], 'uses': ['crust', 'topping', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['tree nuts'], 'uses': []},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['dairy'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['eggs', 'soy'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['Egg'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['tree nuts', 'milk'],
               'may_contain': [' sesame ', 'tree nuts'],
               'uses': ['topping']},
     'filling': {'allergens': [' sesame '], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['dairy', ' sesame '], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy', ' sesame '], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [' sesame '], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['milk', 'sesame'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': ['Egg', 'eggs'], 'may_contain': [], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'filling': {'allergens': ['Egg', 'milk'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['tree nuts', 'Egg'], 'uses': ['crust']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk'], 'error': None, 'may_contain': []}]],
 [['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['mystery']},
     'crust': {'allergens': ['eggs', 'peanuts'], 'may_contain': ['eggs'], 'uses': ['topping']},
     'filling': {'allergens': ['Egg', 'peanuts'], 'may_contain': ['Egg'], 'uses': ['topping']},
     'sauce': {'allergens': ['dairy', 'soy'], 'may_contain': ['dairy', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['tree nuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce', 'filling', 'topping', 'mystery']},
     'crust': {'allergens': ['peanuts'], 'may_contain': ['wheat', ' sesame '], 'uses': ['filling']},
     'filling': {'allergens': ['wheat', 'soy'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': ['eggs', 'wheat'], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts', 'wheat'],
               'may_contain': ['tree nuts', ' sesame '],
               'uses': ['filling']},
     'filling': {'allergens': ['peanuts'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['filling']},
     'topping': {'allergens': [], 'may_contain': ['tree nuts', 'Egg'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': ['egg']}],
  ['generated control 2',
   [{'base': {'allergens': ['soy', 'peanuts'], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': []},
     'filling': {'allergens': ['peanuts', 'tree nuts'], 'may_contain': [], 'uses': ['base']},
     'sauce': {'allergens': [' sesame '], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['Egg', 'wheat'], 'uses': ['topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'soy'], 'uses': ['filling']},
     'filling': {'allergens': ['wheat'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat'], 'may_contain': ['milk'], 'uses': ['crust', 'base']},
     'topping': {'allergens': ['eggs'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': ['egg'], 'error': None, 'may_contain': ['milk', 'wheat']}]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
flat recipe{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}Passed
diamond sharing{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}Passed
cycle{'contains': [], 'error': None, 'may_contain': []}{'contains': [], 'error': 'cycle: base', 'may_contain': []}Failed
regression: error propagation{'contains': ['sesame'], 'error': None, 'may_contain': ['egg', 'tree nut', 'wheat']}{'contains': [], 'error': 'cycle: sauce', 'may_contain': []}Failed
repair check: error propagation{'contains': ['milk', 'soy'], 'error': None, 'may_contain': ['wheat']}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Failed
generated control 1{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}Passed
generated control 2{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}Passed
generated control 3{'contains': ['milk', 'sesame', 'soy', 'tree nut'], 'error': None, 'may_contain': ['egg']}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Failed

SHA-256 / c702dc9e0dac5966b88d8d9afa76a3e3d74d6a806b77619dbdc1228239446835

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(recipes, root):
    SYN = {'dairy': 'milk', 'peanuts': 'peanut', 'tree nuts': 'tree nut', 'eggs': 'egg'}
    def canon(a):
        a = a.strip().lower()
        return SYN.get(a, a)
    contains, may = set(), set()
    state = {}
    def visit(n):
        if n not in recipes:
            return 'unknown: ' + n
        if state.get(n) == 1:
            return 'cycle: ' + n
        if state.get(n) == 2:
            return None
        state[n] = 1
        r = recipes[n]
        contains.update(canon(a) for a in r.get('allergens', []))
        may.update(canon(a) for a in r.get('may_contain', []))
        for s in r.get('uses', []):
            e = visit(s)
            if e and e.startswith('cycle'):
                return e
        state[n] = 2
        return None
    err = visit(root)
    if err:
        return {'contains': [], 'may_contain': [], 'error': err}
    return {'contains': sorted(contains), 'may_contain': sorted(may - contains), 'error': None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce']},
     'crust': {'allergens': [], 'may_contain': ['eggs'], 'uses': ['filling', 'topping', 'sauce']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame '],
               'may_contain': ['tree nuts', 'wheat'],
               'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'cycle: sauce', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['soy'], 'may_contain': ['wheat', 'milk'], 'uses': ['topping', 'mystery']},
     'crust': {'allergens': ['dairy', 'peanuts'], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['sauce']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust']},
     'topping': {'allergens': ['milk'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['dairy'], 'may_contain': [], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['tree nuts'], 'may_contain': ['milk'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['peanuts', 'soy'], 'may_contain': [' sesame '], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['peanuts', 'wheat'], 'uses': ['crust', 'filling']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['dairy', 'milk'], 'uses': ['filling']},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': []},
     'topping': {'allergens': [], 'may_contain': ['peanuts', 'milk'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['sauce', 'filling', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['peanuts', 'eggs'], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'topping': {'allergens': ['milk', 'tree nuts'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}]],
 [['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': ['Egg'], 'may_contain': ['soy'], 'uses': ['crust', 'filling', 'mystery']},
     'crust': {'allergens': ['milk'], 'may_contain': ['milk'], 'uses': []},
     'filling': {'allergens': ['eggs', 'milk'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['sauce', 'mystery']},
     'crust': {'allergens': ['eggs'], 'may_contain': ['soy'], 'uses': ['topping', 'base']},
     'filling': {'allergens': ['soy', 'wheat'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['dairy', 'tree nuts'], 'uses': ['filling']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['wheat', 'milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'crust': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping']},
     'filling': {'allergens': ['milk', 'dairy'], 'may_contain': ['tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'base', 'mystery']},
     'topping': {'allergens': ['Egg', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'peanut'], 'error': None, 'may_contain': ['tree nut']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['eggs', 'soy'], 'uses': ['crust']},
     'crust': {'allergens': [], 'may_contain': ['dairy', 'eggs'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame ', 'tree nuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['wheat'], 'may_contain': [' sesame ', 'tree nuts'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': None, 'may_contain': ['egg', 'milk', 'sesame', 'soy', 'tree nut']}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['soy', 'eggs'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'filling': {'allergens': [' sesame ', 'Egg'], 'may_contain': ['eggs', 'peanuts'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'sesame'], 'error': None, 'may_contain': ['peanut', 'soy']}]],
 [['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['regression: error propagation',
   [{'base': {'allergens': ['milk'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['eggs'], 'may_contain': [' sesame ', 'dairy'], 'uses': []},
     'filling': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'tree nuts'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': ['Egg', 'eggs'], 'may_contain': ['dairy'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['mystery']},
     'filling': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['topping', 'base']},
     'sauce': {'allergens': [], 'may_contain': ['peanuts', 'eggs'], 'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['eggs', 'peanuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['soy'],
              'may_contain': ['dairy', 'wheat'],
              'uses': ['sauce', 'filling', 'topping']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['Egg', 'dairy'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['dairy', 'soy'], 'uses': []},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['Egg'], 'uses': ['crust']},
     'topping': {'allergens': ['soy', 'milk'], 'may_contain': ['tree nuts', 'soy'], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['tree nut', 'wheat']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy'], 'may_contain': ['soy', 'wheat'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'milk'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg', 'tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': ['soy'],
               'may_contain': ['wheat', ' sesame '],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['sesame', 'tree nut', 'wheat']}],
  ['generated control 3',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'crust': {'allergens': ['milk', 'eggs'], 'may_contain': ['wheat'], 'uses': []},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat', 'soy'], 'may_contain': ['eggs', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': []}]],
 [['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [' sesame '], 'may_contain': ['soy', 'wheat'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping', 'mystery']},
     'sauce': {'allergens': [], 'may_contain': [' sesame ', 'soy'], 'uses': []},
     'topping': {'allergens': ['eggs'], 'may_contain': [], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: filling', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['eggs', 'peanuts'], 'may_contain': [], 'uses': ['crust', 'topping', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['tree nuts'], 'uses': []},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['dairy'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['eggs', 'soy'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['Egg'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['tree nuts', 'milk'],
               'may_contain': [' sesame ', 'tree nuts'],
               'uses': ['topping']},
     'filling': {'allergens': [' sesame '], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['dairy', ' sesame '], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy', ' sesame '], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [' sesame '], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['milk', 'sesame'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': ['Egg', 'eggs'], 'may_contain': [], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'filling': {'allergens': ['Egg', 'milk'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['tree nuts', 'Egg'], 'uses': ['crust']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk'], 'error': None, 'may_contain': []}]],
 [['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['mystery']},
     'crust': {'allergens': ['eggs', 'peanuts'], 'may_contain': ['eggs'], 'uses': ['topping']},
     'filling': {'allergens': ['Egg', 'peanuts'], 'may_contain': ['Egg'], 'uses': ['topping']},
     'sauce': {'allergens': ['dairy', 'soy'], 'may_contain': ['dairy', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['tree nuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce', 'filling', 'topping', 'mystery']},
     'crust': {'allergens': ['peanuts'], 'may_contain': ['wheat', ' sesame '], 'uses': ['filling']},
     'filling': {'allergens': ['wheat', 'soy'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': ['eggs', 'wheat'], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts', 'wheat'],
               'may_contain': ['tree nuts', ' sesame '],
               'uses': ['filling']},
     'filling': {'allergens': ['peanuts'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['filling']},
     'topping': {'allergens': [], 'may_contain': ['tree nuts', 'Egg'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': ['egg']}],
  ['generated control 2',
   [{'base': {'allergens': ['soy', 'peanuts'], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': []},
     'filling': {'allergens': ['peanuts', 'tree nuts'], 'may_contain': [], 'uses': ['base']},
     'sauce': {'allergens': [' sesame '], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['Egg', 'wheat'], 'uses': ['topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'soy'], 'uses': ['filling']},
     'filling': {'allergens': ['wheat'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat'], 'may_contain': ['milk'], 'uses': ['crust', 'base']},
     'topping': {'allergens': ['eggs'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': ['egg'], 'error': None, 'may_contain': ['milk', 'wheat']}]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
flat recipe{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}Passed
diamond sharing{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}Passed
cycle{'contains': [], 'error': 'cycle: base', 'may_contain': []}{'contains': [], 'error': 'cycle: base', 'may_contain': []}Passed
regression: error propagation{'contains': [], 'error': 'cycle: sauce', 'may_contain': []}{'contains': [], 'error': 'cycle: sauce', 'may_contain': []}Passed
repair check: error propagation{'contains': ['milk', 'soy'], 'error': None, 'may_contain': ['wheat']}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Failed
generated control 1{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}Passed
generated control 2{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}Passed
generated control 3{'contains': ['milk', 'sesame', 'soy', 'tree nut'], 'error': None, 'may_contain': ['egg']}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Failed

SHA-256 / c14aa39789809bc02c63a7d851b0e8be0117a451510fab5c4791d4ac45974657

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(recipes, root):
    SYN = {'dairy': 'milk', 'peanuts': 'peanut', 'tree nuts': 'tree nut', 'eggs': 'egg'}
    def canon(a):
        a = a.strip().lower()
        return SYN.get(a, a)
    contains, may = set(), set()
    state = {}
    def visit(n):
        if n not in recipes:
            return 'unknown: ' + n
        if state.get(n) == 1:
            return 'cycle: ' + n
        if state.get(n) == 2:
            return None
        state[n] = 1
        r = recipes[n]
        contains.update(canon(a) for a in r.get('allergens', []))
        may.update(canon(a) for a in r.get('may_contain', []))
        for s in r.get('uses', []):
            e = visit(s)
            if e:
                return e
        state[n] = 2
        return None
    err = visit(root)
    if err:
        return {'contains': [], 'may_contain': [], 'error': err}
    return {'contains': sorted(contains), 'may_contain': sorted(may - contains), 'error': None}
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce']},
     'crust': {'allergens': [], 'may_contain': ['eggs'], 'uses': ['filling', 'topping', 'sauce']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame '],
               'may_contain': ['tree nuts', 'wheat'],
               'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'cycle: sauce', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['soy'], 'may_contain': ['wheat', 'milk'], 'uses': ['topping', 'mystery']},
     'crust': {'allergens': ['dairy', 'peanuts'], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['sauce']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust']},
     'topping': {'allergens': ['milk'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['dairy'], 'may_contain': [], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['tree nuts'], 'may_contain': ['milk'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['peanuts', 'soy'], 'may_contain': [' sesame '], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['peanuts', 'wheat'], 'uses': ['crust', 'filling']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['dairy', 'milk'], 'uses': ['filling']},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': []},
     'topping': {'allergens': [], 'may_contain': ['peanuts', 'milk'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['sauce', 'filling', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['peanuts', 'eggs'], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'topping': {'allergens': ['milk', 'tree nuts'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}]],
 [['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': ['Egg'], 'may_contain': ['soy'], 'uses': ['crust', 'filling', 'mystery']},
     'crust': {'allergens': ['milk'], 'may_contain': ['milk'], 'uses': []},
     'filling': {'allergens': ['eggs', 'milk'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['milk'], 'uses': ['filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['sauce', 'mystery']},
     'crust': {'allergens': ['eggs'], 'may_contain': ['soy'], 'uses': ['topping', 'base']},
     'filling': {'allergens': ['soy', 'wheat'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['dairy', 'tree nuts'], 'uses': ['filling']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['wheat', 'milk'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'crust': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping']},
     'filling': {'allergens': ['milk', 'dairy'], 'may_contain': ['tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'base', 'mystery']},
     'topping': {'allergens': ['Egg', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'peanut'], 'error': None, 'may_contain': ['tree nut']}],
  ['generated control 2',
   [{'base': {'allergens': [], 'may_contain': ['eggs', 'soy'], 'uses': ['crust']},
     'crust': {'allergens': [], 'may_contain': ['dairy', 'eggs'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame ', 'tree nuts'], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['wheat'], 'may_contain': [' sesame ', 'tree nuts'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': None, 'may_contain': ['egg', 'milk', 'sesame', 'soy', 'tree nut']}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['soy', 'eggs'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['filling']},
     'filling': {'allergens': [' sesame ', 'Egg'], 'may_contain': ['eggs', 'peanuts'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'sesame'], 'error': None, 'may_contain': ['peanut', 'soy']}]],
 [['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['regression: error propagation',
   [{'base': {'allergens': ['milk'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['eggs'], 'may_contain': [' sesame ', 'dairy'], 'uses': []},
     'filling': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'tree nuts'],
               'may_contain': [' sesame ', 'peanuts'],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': ['Egg', 'eggs'], 'may_contain': ['dairy'], 'uses': ['mystery']}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': ['mystery']},
     'filling': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['topping', 'base']},
     'sauce': {'allergens': [], 'may_contain': ['peanuts', 'eggs'], 'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': ['eggs', 'peanuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['soy'],
              'may_contain': ['dairy', 'wheat'],
              'uses': ['sauce', 'filling', 'topping']},
     'crust': {'allergens': ['dairy'], 'may_contain': ['Egg', 'dairy'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['dairy', 'soy'], 'uses': []},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['Egg'], 'uses': ['crust']},
     'topping': {'allergens': ['soy', 'milk'], 'may_contain': ['tree nuts', 'soy'], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['tree nut', 'wheat']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy'], 'may_contain': ['soy', 'wheat'], 'uses': ['sauce', 'topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'milk'], 'uses': ['topping']},
     'filling': {'allergens': [], 'may_contain': ['Egg', 'tree nuts'], 'uses': ['topping']},
     'sauce': {'allergens': ['soy'],
               'may_contain': ['wheat', ' sesame '],
               'uses': ['crust', 'filling', 'topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'soy'], 'error': None, 'may_contain': ['sesame', 'tree nut', 'wheat']}],
  ['generated control 3',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'crust': {'allergens': ['milk', 'eggs'], 'may_contain': ['wheat'], 'uses': []},
     'filling': {'allergens': ['peanuts', 'wheat'], 'may_contain': ['peanuts', 'wheat'], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat', 'soy'], 'may_contain': ['eggs', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': ['wheat'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': []}]],
 [['unknown sub', [{'base': {'uses': ['ghost']}}, 'base'],
   {'contains': [], 'error': 'unknown: ghost', 'may_contain': []}],
  ['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [' sesame '], 'may_contain': ['soy', 'wheat'], 'uses': ['filling']},
     'filling': {'allergens': [], 'may_contain': [' sesame '], 'uses': ['topping', 'mystery']},
     'sauce': {'allergens': [], 'may_contain': [' sesame ', 'soy'], 'uses': []},
     'topping': {'allergens': ['eggs'], 'may_contain': [], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: filling', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': ['eggs', 'peanuts'], 'may_contain': [], 'uses': ['crust', 'topping', 'mystery']},
     'crust': {'allergens': ['Egg'], 'may_contain': ['tree nuts'], 'uses': []},
     'filling': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['soy', 'Egg'], 'may_contain': ['dairy'], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['eggs', 'soy'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['Egg'], 'may_contain': [], 'uses': ['crust']},
     'crust': {'allergens': ['tree nuts', 'milk'],
               'may_contain': [' sesame ', 'tree nuts'],
               'uses': ['topping']},
     'filling': {'allergens': [' sesame '], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['dairy', ' sesame '], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk', 'tree nut'], 'error': None, 'may_contain': ['sesame']}],
  ['generated control 2',
   [{'base': {'allergens': ['dairy', ' sesame '], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': []},
     'filling': {'allergens': [' sesame ', 'soy'], 'may_contain': [' sesame '], 'uses': ['topping']},
     'sauce': {'allergens': [], 'may_contain': [], 'uses': ['topping']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['milk', 'sesame'], 'error': None, 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': ['Egg', 'eggs'], 'may_contain': [], 'uses': ['crust', 'filling']},
     'crust': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']},
     'filling': {'allergens': ['Egg', 'milk'], 'may_contain': [], 'uses': []},
     'sauce': {'allergens': ['eggs'], 'may_contain': ['tree nuts', 'Egg'], 'uses': ['crust']},
     'topping': {'allergens': [], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': ['egg', 'milk'], 'error': None, 'may_contain': []}]],
 [['flat recipe', [{'base': {'allergens': ['milk'], 'may_contain': ['soy'], 'uses': []}}, 'base'],
   {'contains': ['milk'], 'error': None, 'may_contain': ['soy']}],
  ['diamond sharing',
   [{'a': {'allergens': ['wheat'], 'uses': ['c']},
     'b': {'allergens': [], 'uses': ['c']},
     'base': {'allergens': [], 'uses': ['a', 'b']},
     'c': {'allergens': ['Dairy'], 'uses': []}},
    'base'],
   {'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}],
  ['cycle', [{'a': {'uses': ['base']}, 'base': {'uses': ['a']}}, 'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['regression: error propagation',
   [{'base': {'allergens': [], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['mystery']},
     'crust': {'allergens': ['eggs', 'peanuts'], 'may_contain': ['eggs'], 'uses': ['topping']},
     'filling': {'allergens': ['Egg', 'peanuts'], 'may_contain': ['Egg'], 'uses': ['topping']},
     'sauce': {'allergens': ['dairy', 'soy'], 'may_contain': ['dairy', ' sesame '], 'uses': ['topping']},
     'topping': {'allergens': ['eggs', 'wheat'], 'may_contain': ['tree nuts'], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['repair check: error propagation',
   [{'base': {'allergens': [], 'may_contain': [], 'uses': ['sauce', 'filling', 'topping', 'mystery']},
     'crust': {'allergens': ['peanuts'], 'may_contain': ['wheat', ' sesame '], 'uses': ['filling']},
     'filling': {'allergens': ['wheat', 'soy'], 'may_contain': ['peanuts'], 'uses': []},
     'sauce': {'allergens': ['eggs', 'wheat'], 'may_contain': [], 'uses': ['crust', 'topping']},
     'topping': {'allergens': ['dairy', 'peanuts'], 'may_contain': [], 'uses': []}},
    'base'],
   {'contains': [], 'error': 'unknown: mystery', 'may_contain': []}],
  ['generated control 1',
   [{'base': {'allergens': ['tree nuts'], 'may_contain': [], 'uses': ['topping']},
     'crust': {'allergens': ['tree nuts', 'wheat'],
               'may_contain': ['tree nuts', ' sesame '],
               'uses': ['filling']},
     'filling': {'allergens': ['peanuts'], 'may_contain': ['wheat'], 'uses': ['topping']},
     'sauce': {'allergens': [' sesame ', 'eggs'], 'may_contain': ['tree nuts', 'wheat'], 'uses': ['filling']},
     'topping': {'allergens': [], 'may_contain': ['tree nuts', 'Egg'], 'uses': []}},
    'base'],
   {'contains': ['tree nut'], 'error': None, 'may_contain': ['egg']}],
  ['generated control 2',
   [{'base': {'allergens': ['soy', 'peanuts'], 'may_contain': ['tree nuts'], 'uses': ['crust', 'topping']},
     'crust': {'allergens': [], 'may_contain': [], 'uses': []},
     'filling': {'allergens': ['peanuts', 'tree nuts'], 'may_contain': [], 'uses': ['base']},
     'sauce': {'allergens': [' sesame '], 'may_contain': [], 'uses': ['crust', 'filling']},
     'topping': {'allergens': [], 'may_contain': ['Egg'], 'uses': ['filling']}},
    'base'],
   {'contains': [], 'error': 'cycle: base', 'may_contain': []}],
  ['generated control 3',
   [{'base': {'allergens': [], 'may_contain': ['Egg', 'wheat'], 'uses': ['topping']},
     'crust': {'allergens': ['Egg'], 'may_contain': [' sesame ', 'soy'], 'uses': ['filling']},
     'filling': {'allergens': ['wheat'], 'may_contain': [], 'uses': ['topping']},
     'sauce': {'allergens': ['wheat'], 'may_contain': ['milk'], 'uses': ['crust', 'base']},
     'topping': {'allergens': ['eggs'], 'may_contain': ['milk'], 'uses': []}},
    'base'],
   {'contains': ['egg'], 'error': None, 'may_contain': ['milk', 'wheat']}]]]
for label, args, expected in fixtures[N - 1]:
    check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
flat recipe{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}{'contains': ['milk'], 'error': None, 'may_contain': ['soy']}Passed
diamond sharing{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'wheat'], 'error': None, 'may_contain': []}Passed
cycle{'contains': [], 'error': 'cycle: base', 'may_contain': []}{'contains': [], 'error': 'cycle: base', 'may_contain': []}Passed
regression: error propagation{'contains': [], 'error': 'cycle: sauce', 'may_contain': []}{'contains': [], 'error': 'cycle: sauce', 'may_contain': []}Passed
repair check: error propagation{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Passed
generated control 1{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}{'contains': ['milk', 'peanut', 'soy', 'tree nut'], 'error': None, 'may_contain': ['sesame']}Passed
generated control 2{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}{'contains': ['milk', 'peanut', 'wheat'], 'error': None, 'may_contain': []}Passed
generated control 3{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}{'contains': [], 'error': 'unknown: mystery', 'may_contain': []}Passed

SHA-256 / 53b57a17c10a69f735c8707df8873fb1fde82dac2264995123aa4c8d750e6b17

Verification & scope

A deterministic toy contract stated in full here; it is a bounded teaching model, not an authoritative reference or standards implementation. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:52:30.347578+00:00.

Case digest / bb00bbedb9adbe9aa751c05f83573b0b55b6bc360953e5f93e331b877150ae20