{
  "version": 3,
  "sources": ["../../../../src/core/managers/frontier-dependency-manager.ts"],
  "sourcesContent": [
    "import { CellValueNode } from \"../../evaluator/dependency-nodes/cell-value-node.cjs\";\nimport type { CellAddress, CellInRangeResult, RangeAddress } from \"../types.cjs\";\nimport { cellAddressToKey, checkRangeIntersection } from \"../utils.cjs\";\nimport type { DependencyManager } from \"./dependency-manager.cjs\";\nimport type { DependencyNode } from \"./dependency-node.cjs\";\nimport type { WorkbookManager } from \"./workbook-manager.cjs\";\nimport type { SpillMetaNode } from \"../../evaluator/dependency-nodes/spill-meta-node.cjs\";\n\ntype EvalOrderEntry =\n  | {\n      type: \"value\";\n      address: CellAddress;\n      node: CellValueNode;\n    }\n  | {\n      type: \"empty_cell\";\n      address: CellAddress;\n      candidates: SpillMetaNode[];\n    }\n  | {\n      type: \"empty_range\";\n      address: RangeAddress;\n      candidates: SpillMetaNode[];\n    };\n\nexport class FrontierDependencyManager {\n  private evalOrder: EvalOrderEntry[] = [];\n  private _resolved: boolean = false;\n  private _directDepsUpdated: boolean = false;\n  private evalOrderInitialized: boolean = false;\n\n  constructor(\n    protected readonly frontierRange: RangeAddress,\n    protected workbookManager: WorkbookManager,\n    protected evaluationManager: DependencyManager,\n    options?: { skipInitialBuild?: boolean }\n  ) {\n    if (options?.skipInitialBuild) {\n      return;\n    }\n\n    this.buildInitialEvalOrder();\n  }\n\n  protected buildInitialEvalOrder() {\n    this.evalOrderInitialized = true;\n    this.evalOrder = [];\n    this._frontierDependencies = new Set();\n    this._discardedFrontierDependencies = new Set();\n    this._dependencies = new Set();\n\n    const addressToSpillMetaNode = (address: CellAddress) => {\n      const node = this.evaluationManager.getSpillMetaNode(\n        cellAddressToKey(address).replace(/^[^:]+:/, \"spill-meta:\")\n      );\n      return node;\n    };\n    // todo maybe pass in lookupOrder\n    let directDepsUpdated = false;\n    this.evalOrder = this.workbookManager\n      .buildRangeEvalOrder(\"col-major\", this.frontierRange)\n      .map((entry): EvalOrderEntry => {\n        if (entry.type === \"value\") {\n          const addressToNode = (address: CellAddress) => {\n            const node = this.evaluationManager.getCellValueNode(\n              cellAddressToKey(address)\n            );\n            return node;\n          };\n          return {\n            type: \"value\",\n            address: entry.address,\n            node: addressToNode(entry.address),\n          };\n        } else if (entry.type === \"empty_cell\") {\n          return {\n            type: \"empty_cell\",\n            address: entry.address,\n            candidates: entry.candidates.map(addressToSpillMetaNode),\n          };\n        } else if (entry.type === \"empty_range\") {\n          return {\n            type: \"empty_range\",\n            address: entry.address,\n            candidates: entry.candidates.map(addressToSpillMetaNode),\n          };\n        }\n        throw new Error(\"Invalid entry type: \" + (entry as any).type);\n      });\n    for (const entry of this.evalOrder) {\n      if (entry.type === \"empty_cell\" || entry.type === \"empty_range\") {\n        for (const candidate of entry.candidates) {\n          this._frontierDependencies.add(candidate);\n          directDepsUpdated = true;\n        }\n      } else if (entry.type === \"value\") {\n        this.addDependency(entry.node);\n        directDepsUpdated = true;\n      }\n    }\n    this._directDepsUpdated = directDepsUpdated;\n  }\n\n  protected ensureEvalOrderBuilt() {\n    if (!this.evalOrderInitialized) {\n      this.buildInitialEvalOrder();\n    }\n  }\n\n  /**\n   * frontierDependencies is the set of dependency node keys that could spill values onto the target range (if evaluationResult is spilled-values)\n   * Key is from cellAddressToKey\n   *\n   * soft edge dependencies, which can not cause cycles in the dependency graph\n   */\n  private _frontierDependencies: Set<SpillMetaNode> = new Set();\n\n  /**\n   * discardedFrontierDependencies is the set of dependency node keys that were discarded as frontier dependencies because\n   * they they do not produce spilled values that spill onto the target range\n   * Key is from cellAddressToKey\n   */\n  private _discardedFrontierDependencies: Set<SpillMetaNode> = new Set();\n\n  /**\n   * hard edge dependencies, which can cause cycles in the dependency graph\n   */\n  private _dependencies: Set<DependencyNode> = new Set();\n\n  /**\n   * cache, should maybe be stored in the cache manager\n   */\n  get iterateAllCells(): undefined | Iterable<CellInRangeResult> {\n    return undefined;\n  }\n\n  public getRangeEvalOrder() {\n    this.ensureEvalOrderBuilt();\n    return this.evalOrder;\n  }\n\n  public getFrontierRange() {\n    return this.frontierRange;\n  }\n\n  public restoreResolvedSnapshot(options: {\n    dependencies: Set<DependencyNode>;\n  }) {\n    this.evalOrder = [];\n    this.evalOrderInitialized = true;\n    this._frontierDependencies = new Set();\n    this._discardedFrontierDependencies = new Set();\n    this._dependencies = new Set(options.dependencies);\n    this._directDepsUpdated = false;\n    this._resolved = true;\n  }\n\n  public invalidate() {\n    this.evalOrder = [];\n    this.evalOrderInitialized = false;\n    this._frontierDependencies = new Set();\n    this._discardedFrontierDependencies = new Set();\n    this._dependencies = new Set();\n    this._directDepsUpdated = false;\n    this._resolved = false;\n  }\n\n  public get frontierDependencies() {\n    this.ensureEvalOrderBuilt();\n    return this._frontierDependencies\n      .difference(this._discardedFrontierDependencies)\n      .difference(this._dependencies);\n  }\n\n  public get discardedFrontierDependencies() {\n    this.ensureEvalOrderBuilt();\n    return this._discardedFrontierDependencies;\n  }\n\n  public maybeDiscardFrontierDependency(dependency: SpillMetaNode) {\n    if (!dependency.resolved && !dependency.canResolve()) {\n      return;\n    }\n    if (this._discardedFrontierDependencies.has(dependency)) {\n      return;\n    }\n    this._directDepsUpdated = true;\n    this._discardedFrontierDependencies.add(dependency);\n  }\n\n  public maybeUpgradeFrontierDependency(dependency: SpillMetaNode) {\n    if (!dependency.resolved && !dependency.canResolve()) {\n      return;\n    }\n    if (this._dependencies.has(dependency)) {\n      return;\n    }\n    this._directDepsUpdated = true;\n    this._dependencies.add(dependency);\n  }\n\n  /**\n   * a range is considered resolved when the dependencies has been established\n   */\n  public resolve() {\n    if (this.canResolve()) {\n      this._resolved = true;\n    }\n  }\n\n  public canResolve() {\n    return !this._directDepsUpdated && this.frontierDependencies.size === 0;\n  }\n\n  public get resolved() {\n    return this._resolved;\n  }\n\n  public get directDepsUpdated() {\n    return this._directDepsUpdated;\n  }\n\n  public resetDirectDepsUpdated() {\n    if (this._resolved) {\n      return;\n    }\n\n    this._directDepsUpdated = false;\n  }\n\n  public getDependencies() {\n    this.ensureEvalOrderBuilt();\n    return this._dependencies;\n  }\n\n  public getFrontierDependencies() {\n    return this.frontierDependencies;\n  }\n\n  public getAllDependencies() {\n    this.ensureEvalOrderBuilt();\n    return this._dependencies.union(this.frontierDependencies);\n  }\n\n  public getDiscardedFrontierDependencies() {\n    return this.discardedFrontierDependencies;\n  }\n\n  public addDependency(dependency: DependencyNode) {\n    this._dependencies.add(dependency);\n  }\n\n  public upgradeFrontierDependencies() {\n    // todo can be optimized to not generate the frontier candidates every time\n    // we can cache the frontier candidates for the current cell\n    const frontierCandidates: SpillMetaNode[] = Array.from(\n      this.frontierDependencies\n    );\n\n    for (const candidateNode of frontierCandidates) {\n      const result = candidateNode.evaluationResult;\n\n      // upgrade or downgrade frontier dependency\n      if (result.type === \"spilled-values\") {\n        const spillArea = result.spillArea(candidateNode.cellAddress);\n        const intersects = checkRangeIntersection(\n          this.frontierRange.range,\n          spillArea\n        );\n        if (intersects) {\n          this.maybeUpgradeFrontierDependency(candidateNode); // upgraded!\n        } else {\n          this.maybeDiscardFrontierDependency(candidateNode); // downgraded!\n        }\n      } else {\n        this.maybeDiscardFrontierDependency(candidateNode); // downgraded!\n      }\n    }\n  }\n}\n"
  ],
  "mappings": ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;AAEyD,IAAzD;AAAA;AAuBO,MAAM,0BAA0B;AAAA,EAOhB;AAAA,EACT;AAAA,EACA;AAAA,EARJ,YAA8B,CAAC;AAAA,EAC/B,YAAqB;AAAA,EACrB,qBAA8B;AAAA,EAC9B,uBAAgC;AAAA,EAExC,WAAW,CACU,eACT,iBACA,mBACV,SACA;AAAA,IAJmB;AAAA,IACT;AAAA,IACA;AAAA,IAGV,IAAI,SAAS,kBAAkB;AAAA,MAC7B;AAAA,IACF;AAAA,IAEA,KAAK,sBAAsB;AAAA;AAAA,EAGnB,qBAAqB,GAAG;AAAA,IAChC,KAAK,uBAAuB;AAAA,IAC5B,KAAK,YAAY,CAAC;AAAA,IAClB,KAAK,wBAAwB,IAAI;AAAA,IACjC,KAAK,iCAAiC,IAAI;AAAA,IAC1C,KAAK,gBAAgB,IAAI;AAAA,IAEzB,MAAM,yBAAyB,CAAC,YAAyB;AAAA,MACvD,MAAM,OAAO,KAAK,kBAAkB,iBAClC,8BAAiB,OAAO,EAAE,QAAQ,WAAW,aAAa,CAC5D;AAAA,MACA,OAAO;AAAA;AAAA,IAGT,IAAI,oBAAoB;AAAA,IACxB,KAAK,YAAY,KAAK,gBACnB,oBAAoB,aAAa,KAAK,aAAa,EACnD,IAAI,CAAC,UAA0B;AAAA,MAC9B,IAAI,MAAM,SAAS,SAAS;AAAA,QAC1B,MAAM,gBAAgB,CAAC,YAAyB;AAAA,UAC9C,MAAM,OAAO,KAAK,kBAAkB,iBAClC,8BAAiB,OAAO,CAC1B;AAAA,UACA,OAAO;AAAA;AAAA,QAET,OAAO;AAAA,UACL,MAAM;AAAA,UACN,SAAS,MAAM;AAAA,UACf,MAAM,cAAc,MAAM,OAAO;AAAA,QACnC;AAAA,MACF,EAAO,SAAI,MAAM,SAAS,cAAc;AAAA,QACtC,OAAO;AAAA,UACL,MAAM;AAAA,UACN,SAAS,MAAM;AAAA,UACf,YAAY,MAAM,WAAW,IAAI,sBAAsB;AAAA,QACzD;AAAA,MACF,EAAO,SAAI,MAAM,SAAS,eAAe;AAAA,QACvC,OAAO;AAAA,UACL,MAAM;AAAA,UACN,SAAS,MAAM;AAAA,UACf,YAAY,MAAM,WAAW,IAAI,sBAAsB;AAAA,QACzD;AAAA,MACF;AAAA,MACA,MAAM,IAAI,MAAM,yBAA0B,MAAc,IAAI;AAAA,KAC7D;AAAA,IACH,WAAW,SAAS,KAAK,WAAW;AAAA,MAClC,IAAI,MAAM,SAAS,gBAAgB,MAAM,SAAS,eAAe;AAAA,QAC/D,WAAW,aAAa,MAAM,YAAY;AAAA,UACxC,KAAK,sBAAsB,IAAI,SAAS;AAAA,UACxC,oBAAoB;AAAA,QACtB;AAAA,MACF,EAAO,SAAI,MAAM,SAAS,SAAS;AAAA,QACjC,KAAK,cAAc,MAAM,IAAI;AAAA,QAC7B,oBAAoB;AAAA,MACtB;AAAA,IACF;AAAA,IACA,KAAK,qBAAqB;AAAA;AAAA,EAGlB,oBAAoB,GAAG;AAAA,IAC/B,IAAI,CAAC,KAAK,sBAAsB;AAAA,MAC9B,KAAK,sBAAsB;AAAA,IAC7B;AAAA;AAAA,EASM,wBAA4C,IAAI;AAAA,EAOhD,iCAAqD,IAAI;AAAA,EAKzD,gBAAqC,IAAI;AAAA,MAK7C,eAAe,GAA4C;AAAA,IAC7D;AAAA;AAAA,EAGK,iBAAiB,GAAG;AAAA,IACzB,KAAK,qBAAqB;AAAA,IAC1B,OAAO,KAAK;AAAA;AAAA,EAGP,gBAAgB,GAAG;AAAA,IACxB,OAAO,KAAK;AAAA;AAAA,EAGP,uBAAuB,CAAC,SAE5B;AAAA,IACD,KAAK,YAAY,CAAC;AAAA,IAClB,KAAK,uBAAuB;AAAA,IAC5B,KAAK,wBAAwB,IAAI;AAAA,IACjC,KAAK,iCAAiC,IAAI;AAAA,IAC1C,KAAK,gBAAgB,IAAI,IAAI,QAAQ,YAAY;AAAA,IACjD,KAAK,qBAAqB;AAAA,IAC1B,KAAK,YAAY;AAAA;AAAA,EAGZ,UAAU,GAAG;AAAA,IAClB,KAAK,YAAY,CAAC;AAAA,IAClB,KAAK,uBAAuB;AAAA,IAC5B,KAAK,wBAAwB,IAAI;AAAA,IACjC,KAAK,iCAAiC,IAAI;AAAA,IAC1C,KAAK,gBAAgB,IAAI;AAAA,IACzB,KAAK,qBAAqB;AAAA,IAC1B,KAAK,YAAY;AAAA;AAAA,MAGR,oBAAoB,GAAG;AAAA,IAChC,KAAK,qBAAqB;AAAA,IAC1B,OAAO,KAAK,sBACT,WAAW,KAAK,8BAA8B,EAC9C,WAAW,KAAK,aAAa;AAAA;AAAA,MAGvB,6BAA6B,GAAG;AAAA,IACzC,KAAK,qBAAqB;AAAA,IAC1B,OAAO,KAAK;AAAA;AAAA,EAGP,8BAA8B,CAAC,YAA2B;AAAA,IAC/D,IAAI,CAAC,WAAW,YAAY,CAAC,WAAW,WAAW,GAAG;AAAA,MACpD;AAAA,IACF;AAAA,IACA,IAAI,KAAK,+BAA+B,IAAI,UAAU,GAAG;AAAA,MACvD;AAAA,IACF;AAAA,IACA,KAAK,qBAAqB;AAAA,IAC1B,KAAK,+BAA+B,IAAI,UAAU;AAAA;AAAA,EAG7C,8BAA8B,CAAC,YAA2B;AAAA,IAC/D,IAAI,CAAC,WAAW,YAAY,CAAC,WAAW,WAAW,GAAG;AAAA,MACpD;AAAA,IACF;AAAA,IACA,IAAI,KAAK,cAAc,IAAI,UAAU,GAAG;AAAA,MACtC;AAAA,IACF;AAAA,IACA,KAAK,qBAAqB;AAAA,IAC1B,KAAK,cAAc,IAAI,UAAU;AAAA;AAAA,EAM5B,OAAO,GAAG;AAAA,IACf,IAAI,KAAK,WAAW,GAAG;AAAA,MACrB,KAAK,YAAY;AAAA,IACnB;AAAA;AAAA,EAGK,UAAU,GAAG;AAAA,IAClB,OAAO,CAAC,KAAK,sBAAsB,KAAK,qBAAqB,SAAS;AAAA;AAAA,MAG7D,QAAQ,GAAG;AAAA,IACpB,OAAO,KAAK;AAAA;AAAA,MAGH,iBAAiB,GAAG;AAAA,IAC7B,OAAO,KAAK;AAAA;AAAA,EAGP,sBAAsB,GAAG;AAAA,IAC9B,IAAI,KAAK,WAAW;AAAA,MAClB;AAAA,IACF;AAAA,IAEA,KAAK,qBAAqB;AAAA;AAAA,EAGrB,eAAe,GAAG;AAAA,IACvB,KAAK,qBAAqB;AAAA,IAC1B,OAAO,KAAK;AAAA;AAAA,EAGP,uBAAuB,GAAG;AAAA,IAC/B,OAAO,KAAK;AAAA;AAAA,EAGP,kBAAkB,GAAG;AAAA,IAC1B,KAAK,qBAAqB;AAAA,IAC1B,OAAO,KAAK,cAAc,MAAM,KAAK,oBAAoB;AAAA;AAAA,EAGpD,gCAAgC,GAAG;AAAA,IACxC,OAAO,KAAK;AAAA;AAAA,EAGP,aAAa,CAAC,YAA4B;AAAA,IAC/C,KAAK,cAAc,IAAI,UAAU;AAAA;AAAA,EAG5B,2BAA2B,GAAG;AAAA,IAGnC,MAAM,qBAAsC,MAAM,KAChD,KAAK,oBACP;AAAA,IAEA,WAAW,iBAAiB,oBAAoB;AAAA,MAC9C,MAAM,SAAS,cAAc;AAAA,MAG7B,IAAI,OAAO,SAAS,kBAAkB;AAAA,QACpC,MAAM,YAAY,OAAO,UAAU,cAAc,WAAW;AAAA,QAC5D,MAAM,aAAa,oCACjB,KAAK,cAAc,OACnB,SACF;AAAA,QACA,IAAI,YAAY;AAAA,UACd,KAAK,+BAA+B,aAAa;AAAA,QACnD,EAAO;AAAA,UACL,KAAK,+BAA+B,aAAa;AAAA;AAAA,MAErD,EAAO;AAAA,QACL,KAAK,+BAA+B,aAAa;AAAA;AAAA,IAErD;AAAA;AAEJ;",
  "debugId": "353797562488C73964756E2164756E21",
  "names": []
}