1package notebook23import (4 "fmt"5 "slices"6 "strings"7)89// The cells' dependency graph: a cell reading $sales depends on the cell10// giving sales (Vars). A cell's name belongs to the first code cell11// giving it; a later one giving the same name can't run until it's12// renamed. Cells run in the order asked, each after the cells it reads13// among those running, and a cell reading itself, directly or through14// others, doesn't run.1516// Names maps each cell's name to the index of the first code cell17// giving it.18func Names(cells []Cell) map[string]int {19 out := map[string]int{}20 for i, c := range cells {21 if n := c.Name(); n != "" {22 if _, dup := out[n]; !dup {23 out[n] = i24 }25 }26 }27 return out28}2930// Vars maps each variable the cells give others to the index of the31// cell giving it: a cell's name to that cell (Names), and any other32// name a statement assigns to the first code cell assigning it.33func Vars(cells []Cell) map[string]int {34 out := Names(cells)35 for i, c := range cells {36 for _, n := range c.Parse().Assigned() {37 if _, ok := out[n]; !ok {38 out[n] = i39 }40 }41 }42 return out43}4445// Taken says why cell i can't use its name: an earlier cell gives it46// (names ignore case there, as formulas' nu.name do), or "".47func Taken(cells []Cell, i int) string {48 name := cells[i].Name()49 if name == "" {50 return ""51 }52 for j, c := range cells[:i] {53 if strings.EqualFold(c.Name(), name) {54 return fmt.Sprintf("cell %d is already named %s: rename one", j+1, c.Name())55 }56 }57 return ""58}5960// ref is a variable a cell reads from another: its name, and the index61// of the cell giving it.62type ref struct {63 name string64 cell int65}6667// refs are the variables cell i reads from other cells, in the order it68// names them; vars is Vars(cells). A name only it assigns, read before69// it does, is none.70func refs(cells []Cell, vars map[string]int, i int) []ref {71 var out []ref72 for _, n := range cells[i].Parse().Refs() {73 if j, ok := vars[n]; ok && j != i {74 out = append(out, ref{n, j})75 }76 }77 return out78}7980// Reads returns the indices of the cells cell i reads, in the order it81// names them; vars is Vars(cells).82func Reads(cells []Cell, vars map[string]int, i int) []int {83 var out []int84 for _, r := range refs(cells, vars, i) {85 if !slices.Contains(out, r.cell) {86 out = append(out, r.cell)87 }88 }89 return out90}9192// Order returns the code cells of want, each after the cells it reads93// among them, in want's order otherwise, and the cells left out for94// reading themselves, directly or through others.95func Order(cells []Cell, want []int) (order, cycle []int) {96 vars := Vars(cells)97 in := map[int]bool{}98 for _, i := range want {99 if cells[i].Kind == Code {100 in[i] = true101 }102 }103 done := map[int]bool{}104 for len(order) < len(in) {105 progress := false106 for _, i := range want {107 if !in[i] || done[i] {108 continue109 }110 ready := !slices.ContainsFunc(Reads(cells, vars, i), func(j int) bool { return in[j] && !done[j] })111 if ready {112 order, done[i], progress = append(order, i), true, true113 }114 }115 if !progress {116 break117 }118 }119 for _, i := range want {120 if in[i] && !done[i] && !slices.Contains(cycle, i) {121 cycle = append(cycle, i)122 }123 }124 return order, cycle125}126127// Dependents returns the cells that read cell i, directly or through128// others, in the notebook's order.129func Dependents(cells []Cell, i int) []int {130 vars := Vars(cells)131 want := map[int]bool{i: true}132 for changed := true; changed; {133 changed = false134 for j := range cells {135 if !want[j] && cells[j].Kind == Code && slices.ContainsFunc(Reads(cells, vars, j), func(k int) bool { return want[k] }) {136 want[j], changed = true, true137 }138 }139 }140 var out []int141 for j := range cells {142 if want[j] && j != i {143 out = append(out, j)144 }145 }146 return out147}148149// Readable reports whether o, the output of cell c, holds the variable150// name: c's output when c is named so, else a variable it assigns,151// which a file doesn't keep.152func Readable(c Cell, name string, o *Output) bool {153 switch {154 case o == nil || o.NUON == nil:155 return false156 case c.Name() == name:157 return true158 }159 _, ok := o.Vars[name]160 return ok161}162163// Inputs returns the cells cell i reads, directly or through others,164// whose outputs don't hold what it reads (Readable), in the notebook's165// order: what has to run before it can.166func Inputs(cells []Cell, i int, output func(id int) *Output) []int {167 vars := Vars(cells)168 need := map[int]bool{}169 var visit func(j int)170 visit = func(j int) {171 for _, r := range refs(cells, vars, j) {172 if need[r.cell] || r.cell == i {173 continue174 }175 if c := cells[r.cell]; !Readable(c, r.name, output(c.ID)) {176 need[r.cell] = true177 visit(r.cell)178 }179 }180 }181 visit(i)182 var out []int183 for j := range cells {184 if need[j] {185 out = append(out, j)186 }187 }188 return out189}190191// Stale returns the cells, by ID, whose output may not be what running192// them now would give: their source changed since, or an output they193// read changed or is stale itself.194func Stale(cells []Cell, output func(id int) *Output) map[int]bool {195 vars := Vars(cells)196 all := make([]int, len(cells))197 for i := range all {198 all[i] = i199 }200 order, _ := Order(cells, all)201 stale := map[int]bool{}202 for _, i := range order {203 c := cells[i]204 o := output(c.ID)205 if o == nil {206 continue207 }208 s := o.Source != c.Source209 read := map[string]bool{}210 for _, r := range refs(cells, vars, i) {211 read[r.name] = true212 seq := 0213 if d := output(cells[r.cell].ID); d != nil {214 seq = d.Seq215 }216 s = s || stale[cells[r.cell].ID] || o.Reads[r.name] != seq217 }218 for name := range o.Reads {219 s = s || !read[name] // it read a cell it no longer does220 }221 if s {222 stale[c.ID] = true223 }224 }225 return stale226}227228// Settle makes outputs read from a file what their cells' runs would229// have left: made from the source as it is, having read the outputs as230// they are, so none is stale until something changes.231func Settle(cells []Cell, outputs map[int]*Output) {232 vars := Vars(cells)233 for i, c := range cells {234 o := outputs[c.ID]235 if o == nil {236 continue237 }238 o.Source, o.Reads = c.Source, map[string]int{}239 for _, r := range refs(cells, vars, i) {240 o.Reads[r.name] = 0241 if d := outputs[cells[r.cell].ID]; d != nil {242 o.Reads[r.name] = d.Seq243 }244 }245 }246}247248// Caps are how much of the outputs a file keeps, in bytes of NUON: at249// most Cell of one cell's, Total of all of them.250type Caps struct{ Cell, Total int }251252// DefaultCaps keep 1 MB of a cell's output and 8 MB of a notebook's.253var DefaultCaps = Caps{Cell: 1 << 20, Total: 8 << 20}254255// Kept returns the cells, by ID, whose outputs a file keeps within caps:256// in the notebook's order, each that fits in what's left.257func Kept(cells []Cell, output func(id int) *Output, caps Caps) map[int]bool {258 out := map[int]bool{}259 left := caps.Total260 for _, c := range cells {261 o := output(c.ID)262 if o == nil || o.NUON == nil {263 continue264 }265 if n := len(o.NUON); n <= caps.Cell && n <= left {266 out[c.ID] = true267 left -= n268 }269 }270 return out271}