1package sheet23import (4 "slices"56 "src.rest/cat/012/internal/functions"7)89// Running aggregates: within one recalculation, the SUM-like functions10// (SUM, AVERAGE, COUNT, COUNTA, MIN, MAX, PRODUCT) share what they read11// of a range. For each run of columns and first row read more than once,12// the aggregate is kept as a checkpoint after every row with data, read13// forward only as far as some formula has asked. A thousand SUM(A1:A8192) read column A14// once; 8192 running totals SUM($A$1:An) extend the same run one row at15// a time, so they cost O(n) reads instead of O(n^2). Each result is16// accumulated in the same order as reading the range directly, so it is17// the same to the last bit.1819// memoRows is the shortest range, in rows, whose aggregate is shared:20// shorter ones are read directly.21const memoRows = 162223type aggKey struct {24 s *Sheet25 c0, c1, r0 int26}2728// runAgg is a run: the rows read so far with data, and the aggregate29// through each.30type runAgg struct {31 rows []int32 cum []functions.Agg33 next int // every row before next has been read3435 errRow int36 err *Value // the first error met, which ends the run3738 busy bool // being extended: a formula it reads may ask for it again39}4041type aggMemo struct {42 w *Workbook43 m map[aggKey]*runAgg44}4546// RangeAgg returns the aggregate of the range r on the named sheet, or47// false when it should be read directly: no recalculation is running, the48// range is short, its sheet doesn't exist, or a circular reference makes49// the order of evaluation matter.50func (rd *reader) RangeAgg(sheet string, r Rect) (functions.Agg, *Value, bool) {51 memo := rd.memo52 if memo == nil || denseReads || r.To.Row-r.From.Row+1 < memoRows || memo.w.Circular {53 return functions.Agg{}, nil, false54 }55 t := rd.sheet(sheet)56 if t == nil {57 return functions.Agg{}, nil, false58 }59 if _, ok := t.pagedRegion(); ok {60 return functions.Agg{}, nil, false61 }62 key := aggKey{t, r.From.Col, r.To.Col, r.From.Row}63 run := memo.m[key]64 if run == nil {65 // A range read once (a SUM of each named region) is read directly;66 // only the second read of a run starts sharing it.67 memo.m[key] = &runAgg{next: r.From.Row}68 return functions.Agg{}, nil, false69 }70 if run.err == nil && r.To.Row >= run.next {71 if run.busy {72 return functions.Agg{}, nil, false73 }74 circular := memo.w.Circular75 run.extend(rd, t, key, r.To.Row)76 if memo.w.Circular != circular {77 delete(memo.m, key) // it read a cell of a cycle78 }79 }80 return run.through(r.To.Row)81}8283// Fold adds the cells of r to s as SUM-like functions read a range; see84// functions.Book. The engine walks the cells and adds each as it reads85// it, so a range costs no more than a call to Agg.Add per cell.86func (rd *reader) Fold(sheet string, r Rect, s functions.Agg) (functions.Agg, *Value) {87 t := rd.sheet(sheet)88 if t == nil {89 return s, s.Add(ErrRef, false)90 }91 if reg, ok := t.pagedRegion(); ok {92 return rd.pagedFold(t, reg, r, s)93 }94 var e *Value95 add := func(a Addr) bool {96 e = s.Add(rd.read(t, a), false)97 return e == nil98 }99 switch {100 case denseReads:101 for a := r.From; a.Row <= r.To.Row && add(a); {102 if a.Col++; a.Col > r.To.Col {103 a = Addr{Col: r.From.Col, Row: a.Row + 1}104 }105 }106 case r.From.Col == r.To.Col:107 t.cells.colScan(r.From.Col, r.From.Row, r.To.Row, func(row int) bool {108 return add(Addr{Col: r.From.Col, Row: row})109 })110 default:111 for a := range t.cells.keysIn(r) {112 if !add(a) {113 break114 }115 }116 }117 return s, e118}119120// extend reads the run's columns from its next row through to.121func (run *runAgg) extend(rd *reader, t *Sheet, key aggKey, to int) {122 run.busy = true123 defer func() { run.busy = false }()124 cur, row := functions.NewAgg(), -1125 if n := len(run.cum); n > 0 {126 cur = run.cum[n-1]127 }128 visit := func(a Addr) bool {129 if a.Row != row {130 if row >= 0 {131 run.rows, run.cum = append(run.rows, row), append(run.cum, cur)132 }133 row, run.next = a.Row, a.Row134 }135 if e := cur.Add(rd.read(t, a), false); e != nil {136 run.errRow, run.err = a.Row, e137 return false138 }139 return true140 }141 if key.c0 == key.c1 {142 t.cells.colScan(key.c0, run.next, to, func(r int) bool { return visit(Addr{Col: key.c0, Row: r}) })143 } else {144 for a := range t.cells.keysIn(Rect{From: Addr{Col: key.c0, Row: run.next}, To: Addr{Col: key.c1, Row: to}}) {145 if !visit(a) {146 break147 }148 }149 }150 if run.err != nil {151 return152 }153 if row >= 0 {154 run.rows, run.cum = append(run.rows, row), append(run.cum, cur)155 }156 run.next = to + 1157}158159// through is the aggregate from the run's first row through row to.160func (run *runAgg) through(to int) (functions.Agg, *Value, bool) {161 if run.err != nil && to >= run.errRow {162 return functions.Agg{}, run.err, true163 }164 i, found := slices.BinarySearch(run.rows, to)165 if found {166 return run.cum[i], nil, true167 }168 if i == 0 {169 return functions.NewAgg(), nil, true170 }171 return run.cum[i-1], nil, true172}