marimo engine blog

import%20marimo%0A%0A__generated_with%20%3D%20%220.23.11%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20A%20simple%20rendering%20of%20notebook%20using%20marimo%20built-in%20widgets%0A%0A%20%20%20%20Each%20cell%20has%20its%20own%20%60mo.ui.code_editor%60%20and%20some%20controls%20mimicking%20what%20**marimo**%20itself%20has.%20We%20seed%20the%20cells%20with%20our%20own%20example%2C%20but%20feel%20free%20to%20edit%20them%20to%20see%20where%20our%20toy%20approach%20breaks.%20The%20live%20read-outs%20further%20down%20render%20with%20%5B%60mo.ui.table%60%5D(https%3A%2F%2Fdocs.marimo.io%2Fapi%2Finputs%2Ftable%2F%23marimo.ui.table).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20get_cells%2C%20set_cells%20%3D%20mo.state(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22import%20math%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22x%20%3D%202%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22y%20%3D%20x%20%2B%201%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22z%20%3D%20math.sqrt(x%20*%20y)%22%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20)%0A%20%20%20%20return%20get_cells%2C%20set_cells%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(get_cells)%3A%0A%20%20%20%20current_cells%20%3D%20get_cells()%0A%20%20%20%20return%20(current_cells%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(current_cells%2C%20mo%2C%20set_cells)%3A%0A%20%20%20%20def%20_swap(c%2C%20i%2C%20j)%3A%0A%20%20%20%20%20%20%20%20c%20%3D%20list(c)%0A%20%20%20%20%20%20%20%20if%200%20%3C%3D%20j%20%3C%20len(c)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20c%5Bi%5D%2C%20c%5Bj%5D%20%3D%20c%5Bj%5D%2C%20c%5Bi%5D%0A%20%20%20%20%20%20%20%20return%20c%0A%0A%0A%20%20%20%20def%20_set_at(c%2C%20i%2C%20v)%3A%0A%20%20%20%20%20%20%20%20c%20%3D%20list(c)%0A%20%20%20%20%20%20%20%20c%5Bi%5D%20%3D%20v%0A%20%20%20%20%20%20%20%20return%20c%0A%0A%0A%20%20%20%20def%20_insert(c%2C%20i%2C%20v%3D%22%23%20new%20cell%22)%3A%0A%20%20%20%20%20%20%20%20c%20%3D%20list(c)%0A%20%20%20%20%20%20%20%20c.insert(i%2C%20v)%0A%20%20%20%20%20%20%20%20return%20c%0A%0A%0A%20%20%20%20def%20_remove(c%2C%20i)%3A%0A%20%20%20%20%20%20%20%20c%20%3D%20list(c)%0A%20%20%20%20%20%20%20%20if%20len(c)%20%3E%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20del%20c%5Bi%5D%0A%20%20%20%20%20%20%20%20return%20c%0A%0A%0A%20%20%20%20_srcs%20%3D%20current_cells%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_i%2C%20_s%20in%20enumerate(_srcs)%3A%0A%20%20%20%20%20%20%20%20_editor%20%3D%20mo.ui.code_editor(%0A%20%20%20%20%20%20%20%20%20%20%20%20value%3D_s%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20language%3D%22python%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20on_change%3Dlambda%20v%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_set_at(c%2C%20i%2C%20v))%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_controls%20%3D%20mo.hstack(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.md(f%22**Cell%20%7B_i%20%2B%201%7D**%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.ui.button(label%3D%22%E2%9C%95%22%2C%20on_change%3Dlambda%20_%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_remove(c%2C%20i)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.ui.button(label%3D%22%E2%86%91%22%2C%20on_change%3Dlambda%20_%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_swap(c%2C%20i%2C%20i%20-%201)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.ui.button(label%3D%22%E2%86%93%22%2C%20on_change%3Dlambda%20_%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_swap(c%2C%20i%2C%20i%20%2B%201)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.ui.button(label%3D%22%2B%20above%22%2C%20on_change%3Dlambda%20_%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_insert(c%2C%20i)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20mo.ui.button(label%3D%22%2B%20below%22%2C%20on_change%3Dlambda%20_%2C%20i%3D_i%3A%20set_cells(lambda%20c%3A%20_insert(c%2C%20i%20%2B%201)))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20justify%3D%22start%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20gap%3D0.4%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_rows.append(mo.vstack(%5B_controls%2C%20_editor%5D%2C%20gap%3D0.2))%0A%0A%20%20%20%20mo.vstack(_rows)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(current_cells)%3A%0A%20%20%20%20%23%20Let's%20build%20a%20data%20structure%20with%20all%20the%20cells%3A%20%7Bid%3A%20source%7D.%0A%20%20%20%20reader_cells%20%3D%20%7Bi%20%2B%201%3A%20s%20for%20i%2C%20s%20in%20enumerate(current_cells)%7D%0A%20%20%20%20reader_cells%0A%20%20%20%20return%20(reader_cells%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%201.%20Analyze%3A%20what%20each%20cell%20defines%20and%20references%0A%0A%20%20%20%20To%20order%20cells%2C%20we%20first%20need%20to%20know%20how%20they're%20connected.%20A%20cell%20**defines**%20some%20variables%20and%20**references**%20others.%20If%20cell%20B%20references%20%60x%60%20and%20cell%20A%20defines%20%60x%60%2C%20then%20B%20depends%20on%20A.%0A%0A%20%20%20%20Python's%20%60ast%60%20module%20can%20help%20us%20find%20what%20is%20defined%20and%20what%20is%20referenced.%20We'll%20walk%20the%20syntax%20tree%20with%20%5B%60ast.walk%60%5D(https%3A%2F%2Fdocs.python.org%2F3%2Flibrary%2Fast.html%23ast.walk).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20ast%0A%0A%20%20%20%20return%20(ast%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Let's%20parse%20one%20cell%20and%20look%20at%20its%20syntax%20tree.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ast)%3A%0A%20%20%20%20def%20ast_to_tree(node)%3A%0A%20%20%20%20%20%20%20%20if%20isinstance(node%2C%20ast.AST)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20fields%20%3D%20%7Bn%3A%20ast_to_tree(v)%20for%20n%2C%20v%20in%20ast.iter_fields(node)%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%7Btype(node).__name__%3A%20fields%7D%20if%20fields%20else%20type(node).__name__%0A%20%20%20%20%20%20%20%20if%20isinstance(node%2C%20list)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%5Bast_to_tree(n)%20for%20n%20in%20node%5D%0A%20%20%20%20%20%20%20%20return%20repr(node)%0A%0A%20%20%20%20return%20(ast_to_tree%2C)%0A%0A%0A%40app.cell%0Adef%20_(ast%2C%20ast_to_tree%2C%20mo%2C%20reader_cells)%3A%0A%20%20%20%20%23%20AST%20of%20the%20last%20cell%20in%20the%20stack%20(live)%0A%20%20%20%20_last%20%3D%20reader_cells%5Bmax(reader_cells)%5D%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.tree(ast_to_tree(ast.parse(_last)))%0A%20%20%20%20except%20SyntaxError%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20%60%7B_last%7D%60%20won't%20parse%3A%20%7B_e%7D%22)%0A%20%20%20%20_out%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Ok%2C%20I%20can%20see%20that%20%60ast.Name%60%20nodes%20correspond%20to%20variables%2C%20but%20with%20different%20context%20%60ctx%60%3A%20%60Store%60%20vs%20%60Load%60.%20Definitions%20need%20only%20the%20%60Store%60%20ones%20and%20references%20need%20only%20the%20%60Load%60%20ones.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(ast)%3A%0A%20%20%20%20def%20analyze(src)%3A%0A%20%20%20%20%20%20%20%20tree%20%3D%20ast.parse(src)%0A%20%20%20%20%20%20%20%20defs%2C%20refs%20%3D%20set()%2C%20set()%0A%20%20%20%20%20%20%20%20for%20_node%20in%20ast.walk(tree)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20isinstance(_node%2C%20ast.Name)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20isinstance(_node.ctx%2C%20ast.Store)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20defs.add(_node.id)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20isinstance(_node.ctx%2C%20ast.Load)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20refs.add(_node.id)%0A%20%20%20%20%20%20%20%20return%20defs%2C%20refs%0A%0A%20%20%20%20return%20(analyze%2C)%0A%0A%0A%40app.cell%0Adef%20_(analyze%2C%20mo%2C%20reader_cells)%3A%0A%20%20%20%20%23%20Live%3A%20run%20analyze()%20on%20every%20cell%20in%20the%20stack%0A%20%20%20%20def%20_safe_analyze(src)%3A%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20d%2C%20r%20%3D%20analyze(src)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22%2C%20%22.join(sorted(d))%20or%20%22%E2%80%94%22%2C%20%22%2C%20%22.join(sorted(r))%20or%20%22%E2%80%94%22%0A%20%20%20%20%20%20%20%20except%20SyntaxError%20as%20e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22syntax%20error%22%2C%20str(e)%0A%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_cid%2C%20_src%20in%20reader_cells.items()%3A%0A%20%20%20%20%20%20%20%20_d%2C%20_r%20%3D%20_safe_analyze(_src)%0A%20%20%20%20%20%20%20%20_rows.append(%7B%22cell%22%3A%20_cid%2C%20%22code%22%3A%20_src%2C%20%22defines%22%3A%20_d%2C%20%22references%22%3A%20_r%7D)%0A%0A%20%20%20%20mo.ui.table(_rows%2C%20selection%3DNone)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.callout(%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**In%20real%20marimo%20%E2%86%92**%20%5B%60ScopedVisitor%60%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Fmarimo%2Fblob%2Fea3c57c643f57f63a23e44e859c101e56d0b0f82%2Fmarimo%2F_ast%2Fvisitor.py%23L224)%0A%0A%20%20%20%20Real%20marimo%20walks%20the%20AST%20with%20a%20*scope%20stack*%2C%20so%20names%20bound%20inside%20functions%2C%20classes%2C%20or%20comprehensions%20don't%20leak%20out%20as%20cell-level%20variables.%20Our%20flat%20%60ast.walk%60%20would%20wrongly%20count%20those%20as%20definitions.%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20kind%3D%22info%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%202.%20Build%20the%20dependency%20graph%0A%0A%20%20%20%20Now%20that%20each%20cell%20knows%20what%20it%20defines%20and%20references%2C%20we%20can%20connect%20them.%20For%20each%20variable%20a%20cell%20references%2C%20find%20the%20cell%20that%20defines%20it%20%E2%80%94%20that's%20a%20parent.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20We%20need%20to%20create%20an%20index%2C%20which%20variable%20is%20defined%20where.%20We%20can%20create%20a%20dictionary%20%60variable_defs%3D%7Bvariable%3A%20cell_number%7D%60%20to%20keep%20track%20of%20where%20it%20was%20defined.%20If%20we%20ever%20encounter%20a%20problem%2C%20we%20can%20throw%20an%20error%20about%20double%20definition%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(analyze)%3A%0A%20%20%20%20def%20calculate_variable_defs(cells)%3A%0A%20%20%20%20%20%20%20%20_variable_defs%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20_cell%20in%20cells%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_defs%2C%20_%20%3D%20analyze(cells%5B_cell%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_def%20in%20_defs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_variable_defs.update(%7B_def%3A%20_cell%7D)%0A%20%20%20%20%20%20%20%20return%20_variable_defs%0A%0A%20%20%20%20return%20(calculate_variable_defs%2C)%0A%0A%0A%40app.cell%0Adef%20_(calculate_variable_defs%2C%20mo%2C%20reader_cells)%3A%0A%20%20%20%20%23%20Live%3A%20which%20cell%20defines%20each%20variable%3F%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_idx%20%3D%20calculate_variable_defs(reader_cells)%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.ui.table(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%7B%22variable%22%3A%20k%2C%20%22defined%20in%20cell%22%3A%20v%7D%20for%20k%2C%20v%20in%20_idx.items()%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20selection%3DNone%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20except%20SyntaxError%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_out%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20%7B_e%7D%22)%0A%20%20%20%20_out%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20Now%2C%20build%20a%20cell%20dependency%20graph!%0A%0A%20%20%20%20For%20each%20ref%20in%20the%20cell%2C%20find%20where%20it%20was%20defined%2C%20and%20add%20that%20cells%20as%20a%20parent%20in%20the%20graph.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(analyze%2C%20calculate_variable_defs)%3A%0A%20%20%20%20def%20build_deps_graph(cells)%3A%0A%20%20%20%20%20%20%20%20_deps%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20_variable_defs%20%3D%20calculate_variable_defs(cells)%0A%20%20%20%20%20%20%20%20for%20_cell%20in%20cells%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_deps%5B_cell%5D%20%3D%20set()%0A%20%20%20%20%20%20%20%20%20%20%20%20_%2C%20_refs%20%3D%20analyze(cells%5B_cell%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_ref%20in%20_refs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_ref%20in%20_variable_defs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parent_cell%20%3D%20_variable_defs%5B_ref%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_deps%5B_cell%5D.add(parent_cell)%0A%20%20%20%20%20%20%20%20return%20_deps%0A%0A%20%20%20%20return%20(build_deps_graph%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20def%20deps_to_mermaid(deps)%3A%0A%20%20%20%20%20%20%20%20lines%20%3D%20%5B%22graph%20TD%22%5D%0A%20%20%20%20%20%20%20%20for%20node%2C%20parents%20in%20deps.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20not%20parents%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lines.append(f%22%20%20%20%20%7Bnode%7D%22)%20%20%20%20%20%20%20%20%20%20%23%20lone%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20p%20in%20parents%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lines.append(f%22%20%20%20%20%7Bp%7D%20--%3E%20%7Bnode%7D%22)%20%20%20%23%20parent%20--%3E%20child%0A%20%20%20%20%20%20%20%20return%20mo.mermaid(%22%5Cn%22.join(lines))%0A%0A%20%20%20%20return%20(deps_to_mermaid%2C)%0A%0A%0A%40app.cell%0Adef%20_(build_deps_graph%2C%20deps_to_mermaid%2C%20mo%2C%20reader_cells)%3A%0A%20%20%20%20%23%20Live%3A%20the%20dependency%20graph%20of%20the%20cells%20above%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_g%20%3D%20build_deps_graph(reader_cells)%0A%20%20%20%20%20%20%20%20_viz%20%3D%20mo.vstack(%5Bdeps_to_mermaid(_g)%2C%20mo.md(f%22%60%7B_g%7D%60%22)%5D)%0A%20%20%20%20except%20SyntaxError%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_viz%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20%7B_e%7D%22)%0A%20%20%20%20_viz%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.callout(%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**In%20real%20marimo%20%E2%86%92**%20%5B%60DirectedGraph%60%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Fmarimo%2Fblob%2Fea3c57c643f57f63a23e44e859c101e56d0b0f82%2Fmarimo%2F_runtime%2Fdataflow%2Fgraph.py%23L31)%0A%0A%20%20%20%20It%20keeps%20parent%20*and*%20child%20edges%20at%20once%2C%20and%20its%20producer%20index%20maps%20each%20name%20to%20a%20**set**%20of%20cells.%20That%20set%20is%20how%20marimo%20catches%20the%20%22variable%20defined%20in%20two%20cells%22%20error%20%E2%80%94%20our%20index%20just%20lets%20the%20last%20definition%20silently%20win.%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20kind%3D%22info%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%203.%20Topological%20sort%20(Kahn's%20algorithm)%0A%0A%20%20%20%20We%20have%20a%20graph%20of%20who-depends-on-whom.%20Now%20we%20need%20a%20valid%20execution%20order%3A%20every%20cell%20must%20run%20*after*%20the%20cells%20it%20depends%20on.%20That's%20a%20%5Btopological%20sort%5D(https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FTopological_sorting)%2C%20and%20it's%20what%20we%20are%20going%20to%20use%20to%20schedule%20cells.%0A%0A%20%20%20%20The%20idea%20(Kahn's%20algorithm)%3A%20repeatedly%20take%20any%20cell%20with%20no%20remaining%20unmet%20dependencies%20(in-degree%200)%2C%20emit%20it%2C%20and%20remove%20it%20from%20the%20graph%20%E2%80%94%20which%20may%20free%20up%20new%20cells.%20If%20we%20ever%20get%20stuck%20with%20cells%20left%20but%20none%20ready%2C%20there's%20a%20cycle.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20def%20remove_node(graph%2C%20name)%3A%0A%20%20%20%20%20%20%20%20%23%20Find%20all%20nodes%20where%20%60name%60%20is%20the%20parent%0A%20%20%20%20%20%20%20%20for%20dep%2C%20parents%20in%20graph.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20name%20in%20parents%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20remove%20parent%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20parents.remove(name)%0A%0A%20%20%20%20%20%20%20%20%23%20Now%20drop%20the%20%60name%60%20itself%0A%20%20%20%20%20%20%20%20graph.pop(name)%0A%20%20%20%20%20%20%20%20return%20graph%0A%0A%20%20%20%20def%20find_new_idz_nodes(deps%2C%20idz)%3A%0A%20%20%20%20%20%20%20%20%23%20find%20all%20_new_%20in-degree-zero%20items%0A%20%20%20%20%20%20%20%20for%20dep%2C%20parents%20in%20deps.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(parents)%20%3D%3D%200%20and%20dep%20not%20in%20idz%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20idz.append(dep)%0A%0A%20%20%20%20def%20kahn(deps)%3A%0A%20%20%20%20%20%20%20%20%23%20Create%20a%20deep%20copy%20of%20the%20deps%0A%20%20%20%20%20%20%20%20work%20%3D%20%7Bk%3A%20set(v)%20for%20k%2Cv%20in%20deps.items()%7D%0A%0A%20%20%20%20%20%20%20%20%23%20find%20all%20nodes%20with%20no%20parents%20(in-degree%20%3D%200)%0A%20%20%20%20%20%20%20%20%23%20idz%20%3D%0A%0A%20%20%20%20%20%20%20%20%23%20FIFO%0A%20%20%20%20%20%20%20%20%23%20Iterate%20the%20list%20of%20in-degree-0%20nodes%20and%20remove%20them%20left%20to%20right%0A%20%20%20%20%20%20%20%20%23%20Add%20new%20ones%20on%20the%20right%0A%20%20%20%20%20%20%20%20%23%20initialize%20the%20list%20of%20in-degree-zero%20items%0A%20%20%20%20%20%20%20%20idz%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20sorted%20%3D%20%5B%5D%0A%0A%20%20%20%20%20%20%20%20%23%20seed%20the%20pool%20of%20idz%20items%0A%20%20%20%20%20%20%20%20find_new_idz_nodes(work%2C%20idz)%0A%0A%20%20%20%20%20%20%20%20%23%20loop%3A%20while%20idz%20items%20is%20non-empty%0A%20%20%20%20%20%20%20%20while%20idz%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20n%20%3D%20idz.pop(0)%0A%20%20%20%20%20%20%20%20%20%20%20%20remove_node(work%2C%20n)%0A%20%20%20%20%20%20%20%20%20%20%20%20sorted.append(n)%0A%20%20%20%20%20%20%20%20%20%20%20%20find_new_idz_nodes(work%2C%20idz)%0A%20%20%20%20%20%20%20%20if%20len(sorted)%20%3C%20len(deps)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20raise%20RuntimeError(%22Loop%20detected!%22)%0A%0A%20%20%20%20%20%20%20%20return%20sorted%0A%0A%20%20%20%20return%20(kahn%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20A%20few%20graphs%20to%20sanity-check%20ordering%20and%20cycle%20detection.%20The%20two%20cycles%20(one%20obvious%2C%20one%20hidden%20deeper%20in%20the%20chain)%20should%20both%20be%20caught.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(kahn%2C%20mo)%3A%0A%20%20%20%20_examples%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22simple%22%3A%20%7B%22c%22%3A%20%7B%22a%22%2C%20%22b%22%7D%2C%20%22b%22%3A%20%7B%22a%22%7D%2C%20%22a%22%3A%20set()%2C%20%22d%22%3A%20%7B%22c%22%7D%7D%2C%0A%20%20%20%20%20%20%20%20%22two%20roots%22%3A%20%7B%22x%22%3A%20set()%2C%20%22y%22%3A%20set()%2C%20%22z%22%3A%20%7B%22x%22%2C%20%22y%22%7D%7D%2C%0A%20%20%20%20%20%20%20%20%22direct%20cycle%22%3A%20%7B%22a%22%3A%20%7B%22b%22%7D%2C%20%22b%22%3A%20%7B%22a%22%7D%7D%2C%0A%20%20%20%20%20%20%20%20%22hidden%20cycle%22%3A%20%7B%22b%22%3A%20%7B%22a%22%2C%20%22c%22%7D%2C%20%22c%22%3A%20%7B%22b%22%7D%2C%20%22a%22%3A%20set()%7D%2C%0A%20%20%20%20%7D%0A%20%20%20%20_rows%20%3D%20%5B%5D%0A%20%20%20%20for%20_name%2C%20_g%20in%20_examples.items()%3A%0A%20%20%20%20%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%7B%22graph%22%3A%20_name%2C%20%22kahn(graph)%22%3A%20str(kahn(_g))%7D)%0A%20%20%20%20%20%20%20%20except%20RuntimeError%20as%20_e%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_rows.append(%7B%22graph%22%3A%20_name%2C%20%22kahn(graph)%22%3A%20f%22%E2%9A%A0%EF%B8%8F%20%7B_e%7D%22%7D)%0A%20%20%20%20mo.ui.table(_rows%2C%20selection%3DNone)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(build_deps_graph%2C%20kahn%2C%20mo%2C%20reader_cells)%3A%0A%20%20%20%20%23%20Live%3A%20the%20execution%20order%20of%20the%20cells%20above%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_order%20%3D%20kahn(build_deps_graph(reader_cells))%0A%20%20%20%20%20%20%20%20_ord_view%20%3D%20mo.md(%22**Execution%20order%3A**%20%22%20%2B%20%22%20%E2%86%92%20%22.join(f%22%60cell%20%7Bc%7D%60%22%20for%20c%20in%20_order))%0A%20%20%20%20except%20(RuntimeError%2C%20SyntaxError)%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_ord_view%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20%7B_e%7D%22)%0A%20%20%20%20_ord_view%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.callout(%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**In%20real%20marimo%20%E2%86%92**%20%5B%60topological_sort%60%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Fmarimo%2Fblob%2Fea3c57c643f57f63a23e44e859c101e56d0b0f82%2Fmarimo%2F_runtime%2Fdataflow%2F__init__.py%23L96)%0A%0A%20%20%20%20It's%20the%20same%20Kahn's%20algorithm%2C%20but%20the%20ready-pool%20is%20a%20heap%20ordered%20by%20cell%20position%2C%20so%20ties%20break%20deterministically%20(top-to-bottom).%20Cycles%20are%20caught%20earlier%20%E2%80%94%20the%20moment%20an%20edge%20is%20added%20%E2%80%94%20instead%20of%20our%20%22fewer%20nodes%20came%20out%22%20check%20after%20the%20sort.%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20kind%3D%22info%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%204.%20Run%20the%20cells%20(the%20scheduler)%0A%0A%20%20%20%20We%20have%20an%20order.%20Running%20the%20notebook%20is%20now%20almost%20trivial%3A%20%5B%60exec%60%5D(https%3A%2F%2Fdocs.python.org%2F3%2Flibrary%2Ffunctions.html%23exec)%20each%20cell%20**in%20topological%20order**%20into%20one%20shared%20namespace%2C%20so%20a%20cell%20can%20see%20the%20variables%20defined%20by%20the%20cells%20before%20it.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(build_deps_graph%2C%20kahn)%3A%0A%20%20%20%20def%20run_notebook(cells)%3A%0A%20%20%20%20%20%20%20%20deps%20%3D%20build_deps_graph(cells)%0A%20%20%20%20%20%20%20%20order%20%3D%20kahn(deps)%0A%0A%20%20%20%20%20%20%20%20g%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20for%20cid%20in%20order%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20exec(cells%5Bcid%5D%2C%20g)%0A%0A%20%20%20%20%20%20%20%20g.pop(%22__builtins__%22)%0A%20%20%20%20%20%20%20%20return%20g%0A%0A%20%20%20%20return%20(run_notebook%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20reader_cells%2C%20run_notebook)%3A%0A%20%20%20%20%23%20Live%3A%20actually%20execute%20the%20cells%20above%20and%20show%20the%20resulting%20namespace%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_ns%20%3D%20run_notebook(reader_cells)%0A%20%20%20%20%20%20%20%20_res%20%3D%20mo.ui.table(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%7B%22variable%22%3A%20k%2C%20%22value%22%3A%20repr(v)%5B%3A80%5D%7D%20for%20k%2C%20v%20in%20_ns.items()%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20selection%3DNone%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20except%20Exception%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_res%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20**%7Btype(_e).__name__%7D%3A**%20%7B_e%7D%22)%0A%20%20%20%20_res%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.callout(%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**In%20real%20marimo%20%E2%86%92**%20%5B%60DefaultExecutor.execute_cell%60%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Fmarimo%2Fblob%2Fea3c57c643f57f63a23e44e859c101e56d0b0f82%2Fmarimo%2F_runtime%2Fexecutor%2Fexecutor.py%23L46)%0A%0A%20%20%20%20Each%20cell%20is%20split%20into%20a%20body%20(%60exec%60)%20and%20a%20final%20expression%20(%60eval%60)%20%E2%80%94%20that%20last%20value%20becomes%20the%20cell's%20visible%20output.%20Real%20marimo%20also%20deletes%20a%20cell's%20old%20variables%20before%20re-running%20it%3B%20our%20shared%20namespace%20just%20keeps%20accumulating.%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20kind%3D%22info%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%205.%20Cell%20reactivity%0A%0A%20%20%20%20Now%20that%20we%20can%20build%20and%20execute%20the%20entire%20cell%20graph%2C%20let's%20see%20how%20we%20can%20re-run%20it%20when%20one%20cell%20changes.%0A%0A%20%20%20%20User%20can%20do%20any%20changes%20to%20the%20notebook%2C%20which%20can%20cause%20adding%2Fremoving%20any%20defs%2Frefs.%20Which%20means%20we%20need%20to%20recompute%20defs%2Frefs.%20In%20this%20toy%20scenario%20we%20would%20recompute%20the%20entire%20notebook.%0A%0A%20%20%20%20Next%2C%20we%20need%20a%20new%20mechanism%20to%20mark%20cells%20stale.%20We%20can%20store%20this%20as%20a%20boolean%20attribute%20for%20each%20cell.%20Cell%20object%20needs%20to%20become%20a%20bit%20more%20complicated%20%E2%80%94%20a%20small%20%5Bdataclass%5D(https%3A%2F%2Frealpython.com%2Fpython-data-classes%2F)%20does%20the%20job.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20from%20dataclasses%20import%20dataclass%0A%0A%0A%20%20%20%20%40dataclass%0A%20%20%20%20class%20Cell%3A%0A%20%20%20%20%20%20%20%20code%3A%20str%20%3D%20%22%22%0A%20%20%20%20%20%20%20%20stale%3A%20bool%20%3D%20True%0A%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20def%20reverse_deps(deps)%3A%0A%20%20%20%20%20%20%20%20%22%22%22Invert%20child-%3Eparents%20into%20parent-%3Echildren.%22%22%22%0A%20%20%20%20%20%20%20%20children%20%3D%20%7Bn%3A%20set()%20for%20n%20in%20deps%7D%0A%20%20%20%20%20%20%20%20for%20child%2C%20parents%20in%20deps.items()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20p%20in%20parents%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20children%5Bp%5D.add(child)%0A%20%20%20%20%20%20%20%20return%20children%0A%0A%0A%20%20%20%20def%20descendants(children%2C%20start%2C%20seen%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22All%20cells%20transitively%20downstream%20of%20%60start%60%20(excludes%20start%20itself).%22%22%22%0A%20%20%20%20%20%20%20%20if%20seen%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20seen%20%3D%20set()%0A%20%20%20%20%20%20%20%20for%20child%20in%20children%5Bstart%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20child%20not%20in%20seen%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20seen.add(child)%20%20%20%20%20%20%20%20%20%20%23%20mark%20before%20recursing%20-%3E%20handles%20diamonds%20%2B%20safety%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20descendants(children%2C%20child%2C%20seen)%0A%20%20%20%20%20%20%20%20return%20seen%0A%0A%20%20%20%20return%20descendants%2C%20reverse_deps%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20When%20you%20edit%20a%20cell%2C%20marimo%20doesn't%20re-run%20everything%20%E2%80%94%20it%20re-runs%20that%20cell%20**and%20everything%20transitively%20downstream%20of%20it**.%20Pick%20a%20cell%20below%20to%20see%20which%20cells%20would%20go%20stale.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo%2C%20reader_cells)%3A%0A%20%20%20%20stale_sel%20%3D%20mo.ui.dropdown(%0A%20%20%20%20%20%20%20%20options%3D%7Bf%22cell%20%7Bk%7D%22%3A%20k%20for%20k%20in%20reader_cells%7D%2C%0A%20%20%20%20%20%20%20%20value%3Df%22cell%20%7Bmin(reader_cells)%7D%22%2C%0A%20%20%20%20%20%20%20%20label%3D%22If%20you%20edit...%22%2C%0A%20%20%20%20)%0A%20%20%20%20stale_sel%0A%20%20%20%20return%20(stale_sel%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20build_deps_graph%2C%0A%20%20%20%20descendants%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20reader_cells%2C%0A%20%20%20%20reverse_deps%2C%0A%20%20%20%20stale_sel%2C%0A)%3A%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20_children%20%3D%20reverse_deps(build_deps_graph(reader_cells))%0A%20%20%20%20%20%20%20%20_picked%20%3D%20stale_sel.value%0A%20%20%20%20%20%20%20%20if%20_picked%20is%20None%20or%20_picked%20not%20in%20_children%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_view%20%3D%20mo.md(%22_pick%20a%20cell_%22)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_stale%20%3D%20%7B_picked%7D%20%7C%20descendants(_children%2C%20_picked)%0A%20%20%20%20%20%20%20%20%20%20%20%20_view%20%3D%20mo.md(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22**Would%20re-run%3A**%20%22%20%2B%20%22%2C%20%22.join(f%22%60cell%20%7Bc%7D%60%22%20for%20c%20in%20sorted(_stale))%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20except%20Exception%20as%20_e%3A%0A%20%20%20%20%20%20%20%20_view%20%3D%20mo.md(f%22%E2%9A%A0%EF%B8%8F%20%7B_e%7D%22)%0A%20%20%20%20_view%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.callout(%0A%20%20%20%20%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20**In%20real%20marimo%20%E2%86%92**%20%5B%60transitive_closure%60%5D(https%3A%2F%2Fgithub.com%2Fmarimo-team%2Fmarimo%2Fblob%2Fea3c57c643f57f63a23e44e859c101e56d0b0f82%2Fmarimo%2F_runtime%2Fdataflow%2F__init__.py%23L21)%0A%0A%20%20%20%20One%20BFS%20computes%20downstream%20cells%20from%20edges%20marimo%20keeps%20inverted%20already%2C%20so%20it%20never%20rebuilds%20the%20graph%20the%20way%20we%20do%20on%20every%20edit.%20And%20when%20an%20edit%20*removes*%20a%20variable%2C%20it%20also%20re-runs%20the%20cells%20that%20used%20the%20old%20definition.%0A%20%20%20%20%22%22%22)%2C%0A%20%20%20%20%20%20%20%20kind%3D%22info%22%2C%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A