1package sheet23import (4 "cmp"5 "slices"6)78// Dependents, for tracing (trace.go): the formulas reading a cell, found9// through the indexes recalculation keeps, and Reads, which asks the10// same of one formula, so what draws the sheet can mark the dependents it11// shows without listing them all.1213// DependentLinks returns the formulas that read the cell at a directly:14// through a reference, a range, a named range or a region's name. When15// the formula at a spills, the cells it spills into come first, and the16// formulas reading any of them count too. Formulas on this sheet come in17// row-major order, then those on other sheets in tab order. With max > 018// at most max formulas are found, and more reports that there were19// others: a cell read by a million formulas costs what max does.20func (s *Sheet) DependentLinks(a Addr, max int) (links []Link, more bool) {21 subject := Rect{From: a, To: a}22 if area, ok := s.SpillArea(a); ok && area != subject {23 subject = area24 links = append(links, Link{Target: Target{s, area}, Kind: LinkSpill})25 }26 f := &depFinder{max: max, seen: map[loc]struct{}{}}27 s.readersOf(subject, f)28 found := make([]Link, 0, len(f.seen))29 for l := range f.seen {30 found = append(found, Link{Target: Target{l.s, Rect{From: l.a, To: l.a}}})31 }32 w := s.wb33 rank := func(t *Sheet) int {34 if t == s {35 return -136 }37 return w.Index(t)38 }39 slices.SortFunc(found, func(x, y Link) int {40 return cmp.Or(cmp.Compare(rank(x.Sheet), rank(y.Sheet)),41 cmp.Compare(x.Range.From.Row, y.Range.From.Row), cmp.Compare(x.Range.From.Col, y.Range.From.Col))42 })43 return append(links, found...), f.more44}4546// depFinder collects dependents, up to max when it's positive.47type depFinder struct {48 max int49 seen map[loc]struct{}50 more bool51}5253func (f *depFinder) add(l loc) {54 if _, ok := f.seen[l]; ok || f.more {55 return56 }57 if f.max > 0 && len(f.seen) >= f.max {58 f.more = true59 return60 }61 f.seen[l] = struct{}{}62}6364// readersOf adds the formulas that read any cell of r, on s.65func (s *Sheet) readersOf(r Rect, f *depFinder) {66 s.refReaders(r, f)67 s.rangeUsers.overlapping(r, func(u Addr) { f.add(loc{s, u}) })68 w := s.wb69 for k, users := range w.nameUsers {70 if f.more || !w.namesOverlap(k, s, r) {71 continue72 }73 for u := range users {74 if f.add(u); f.more {75 break76 }77 }78 }79 for u := range w.crossUsers {80 if f.more {81 return82 }83 if c := u.s.cells.get(u.a); c != nil && w.xrefsOverlap(c, s, r) {84 f.add(u)85 }86 }87}8889// refReaders adds the formulas on s with a single-cell reference into90// r, walking whichever is smaller: r's cells or the cells referenced.91func (s *Sheet) refReaders(r Rect, f *depFinder) {92 add := func(users map[Addr]struct{}) {93 for u := range users {94 if f.add(loc{s, u}); f.more {95 return96 }97 }98 }99 if n := (r.To.Row - r.From.Row + 1) * (r.To.Col - r.From.Col + 1); n <= len(s.dependents) {100 for row := r.From.Row; row <= r.To.Row && !f.more; row++ {101 for col := r.From.Col; col <= r.To.Col; col++ {102 add(s.dependents[Addr{Col: col, Row: row}])103 }104 }105 return106 }107 for a, users := range s.dependents {108 if f.more {109 return110 }111 if r.Contains(a) {112 add(users)113 }114 }115}116117// namesOverlap reports whether the name with key k, a named range, a118// table (a region's too) or a region's (nu.sales), stands for cells of119// r on s.120func (w *Workbook) namesOverlap(k string, s *Sheet, r Rect) bool {121 if nm, ok := w.names[k]; ok {122 _, over := intersectRect(nm.Range, r)123 return !nm.Gone() && nm.Sheet == s && over124 }125 if v, ok := w.findTable(k); ok {126 _, over := intersectRect(v.r, r)127 return v.ok && v.s == s && over128 }129 t, table, ok := w.regionName(k)130 if !ok || t != s || table == (Rect{}) {131 return false132 }133 _, over := intersectRect(table, r)134 return over135}136137// xrefsOverlap reports whether c reads cells of r on s through a138// reference that names s.139func (w *Workbook) xrefsOverlap(c *Cell, s *Sheet, r Rect) bool {140 for _, x := range c.xrefs {141 if _, over := intersectRect(x.r, r); over && w.byKey[x.key] == s {142 return true143 }144 }145 return false146}147148// Reads reports whether the formula at u, on s, reads any cell of r on149// t directly: through a reference, a range, a named range or a region's150// name. It costs the formula's references, so asking it of every cell151// on screen is cheap.152func (s *Sheet) Reads(u Addr, t *Sheet, r Rect) bool {153 c, _, _ := s.cells.peek(u)154 if c == nil || !c.IsFormula() {155 return false156 }157 w := s.wb158 if t == s {159 for _, a := range c.refs {160 if r.Contains(a) {161 return true162 }163 }164 for _, g := range c.ranges {165 if _, over := intersectRect(g, r); over {166 return true167 }168 }169 }170 if w.xrefsOverlap(c, t, r) {171 return true172 }173 for _, k := range c.names {174 if w.namesOverlap(k, t, r) {175 return true176 }177 }178 return false179}