tablemap.ts 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377
  1. // Because working with row and column-spanning cells is not quite
  2. // trivial, this code builds up a descriptive structure for a given
  3. // table node. The structures are cached with the (persistent) table
  4. // nodes as key, so that they only have to be recomputed when the
  5. // content of the table changes.
  6. //
  7. // This does mean that they have to store table-relative, not
  8. // document-relative positions. So code that uses them will typically
  9. // compute the start position of the table and offset positions passed
  10. // to or gotten from this structure by that amount.
  11. import { Attrs, Node } from 'prosemirror-model';
  12. import { CellAttrs } from './util';
  13. /**
  14. * @public
  15. */
  16. export type ColWidths = number[];
  17. /**
  18. * @public
  19. */
  20. export type Problem =
  21. | {
  22. type: 'colwidth mismatch';
  23. pos: number;
  24. colwidth: ColWidths;
  25. }
  26. | {
  27. type: 'collision';
  28. pos: number;
  29. row: number;
  30. n: number;
  31. }
  32. | {
  33. type: 'missing';
  34. row: number;
  35. n: number;
  36. }
  37. | {
  38. type: 'overlong_rowspan';
  39. pos: number;
  40. n: number;
  41. };
  42. let readFromCache: (key: Node) => TableMap | undefined;
  43. let addToCache: (key: Node, value: TableMap) => TableMap;
  44. // Prefer using a weak map to cache table maps. Fall back on a
  45. // fixed-size cache if that's not supported.
  46. if (typeof WeakMap != 'undefined') {
  47. // eslint-disable-next-line
  48. let cache = new WeakMap<Node, TableMap>();
  49. readFromCache = (key) => cache.get(key);
  50. addToCache = (key, value) => {
  51. cache.set(key, value);
  52. return value;
  53. };
  54. } else {
  55. const cache: (Node | TableMap)[] = [];
  56. const cacheSize = 10;
  57. let cachePos = 0;
  58. readFromCache = (key) => {
  59. for (let i = 0; i < cache.length; i += 2)
  60. if (cache[i] == key) return cache[i + 1] as TableMap;
  61. };
  62. addToCache = (key, value) => {
  63. if (cachePos == cacheSize) cachePos = 0;
  64. cache[cachePos++] = key;
  65. return (cache[cachePos++] = value);
  66. };
  67. }
  68. /**
  69. * @public
  70. */
  71. export interface Rect {
  72. left: number;
  73. top: number;
  74. right: number;
  75. bottom: number;
  76. }
  77. /**
  78. * A table map describes the structure of a given table. To avoid
  79. * recomputing them all the time, they are cached per table node. To
  80. * be able to do that, positions saved in the map are relative to the
  81. * start of the table, rather than the start of the document.
  82. *
  83. * @public
  84. */
  85. export class TableMap {
  86. constructor(
  87. /**
  88. * The number of columns
  89. */
  90. public width: number,
  91. /**
  92. * The number of rows
  93. */
  94. public height: number,
  95. /**
  96. * A width * height array with the start position of
  97. * the cell covering that part of the table in each slot
  98. */
  99. public map: number[],
  100. /**
  101. * An optional array of problems (cell overlap or non-rectangular
  102. * shape) for the table, used by the table normalizer.
  103. */
  104. public problems: Problem[] | null,
  105. ) {}
  106. // Find the dimensions of the cell at the given position.
  107. findCell(pos: number): Rect {
  108. for (let i = 0; i < this.map.length; i++) {
  109. const curPos = this.map[i];
  110. if (curPos != pos) continue;
  111. const left = i % this.width;
  112. const top = (i / this.width) | 0;
  113. let right = left + 1;
  114. let bottom = top + 1;
  115. for (let j = 1; right < this.width && this.map[i + j] == curPos; j++) {
  116. right++;
  117. }
  118. for (
  119. let j = 1;
  120. bottom < this.height && this.map[i + this.width * j] == curPos;
  121. j++
  122. ) {
  123. bottom++;
  124. }
  125. return { left, top, right, bottom };
  126. }
  127. throw new RangeError(`No cell with offset ${pos} found`);
  128. }
  129. // Find the left side of the cell at the given position.
  130. colCount(pos: number): number {
  131. for (let i = 0; i < this.map.length; i++) {
  132. if (this.map[i] == pos) {
  133. return i % this.width;
  134. }
  135. }
  136. throw new RangeError(`No cell with offset ${pos} found`);
  137. }
  138. // Find the next cell in the given direction, starting from the cell
  139. // at `pos`, if any.
  140. nextCell(pos: number, axis: 'horiz' | 'vert', dir: number): null | number {
  141. const { left, right, top, bottom } = this.findCell(pos);
  142. if (axis == 'horiz') {
  143. if (dir < 0 ? left == 0 : right == this.width) return null;
  144. return this.map[top * this.width + (dir < 0 ? left - 1 : right)];
  145. } else {
  146. if (dir < 0 ? top == 0 : bottom == this.height) return null;
  147. return this.map[left + this.width * (dir < 0 ? top - 1 : bottom)];
  148. }
  149. }
  150. // Get the rectangle spanning the two given cells.
  151. rectBetween(a: number, b: number): Rect {
  152. const {
  153. left: leftA,
  154. right: rightA,
  155. top: topA,
  156. bottom: bottomA,
  157. } = this.findCell(a);
  158. const {
  159. left: leftB,
  160. right: rightB,
  161. top: topB,
  162. bottom: bottomB,
  163. } = this.findCell(b);
  164. return {
  165. left: Math.min(leftA, leftB),
  166. top: Math.min(topA, topB),
  167. right: Math.max(rightA, rightB),
  168. bottom: Math.max(bottomA, bottomB),
  169. };
  170. }
  171. // Return the position of all cells that have the top left corner in
  172. // the given rectangle.
  173. cellsInRect(rect: Rect): number[] {
  174. const result: number[] = [];
  175. const seen: Record<number, boolean> = {};
  176. for (let row = rect.top; row < rect.bottom; row++) {
  177. for (let col = rect.left; col < rect.right; col++) {
  178. const index = row * this.width + col;
  179. const pos = this.map[index];
  180. if (seen[pos]) continue;
  181. seen[pos] = true;
  182. if (
  183. (col == rect.left && col && this.map[index - 1] == pos) ||
  184. (row == rect.top && row && this.map[index - this.width] == pos)
  185. ) {
  186. continue;
  187. }
  188. result.push(pos);
  189. }
  190. }
  191. return result;
  192. }
  193. // Return the position at which the cell at the given row and column
  194. // starts, or would start, if a cell started there.
  195. positionAt(row: number, col: number, table: Node): number {
  196. for (let i = 0, rowStart = 0; ; i++) {
  197. const rowEnd = rowStart + table.child(i).nodeSize;
  198. if (i == row) {
  199. let index = col + row * this.width;
  200. const rowEndIndex = (row + 1) * this.width;
  201. // Skip past cells from previous rows (via rowspan)
  202. while (index < rowEndIndex && this.map[index] < rowStart) index++;
  203. return index == rowEndIndex ? rowEnd - 1 : this.map[index];
  204. }
  205. rowStart = rowEnd;
  206. }
  207. }
  208. // Find the table map for the given table node.
  209. static get(table: Node): TableMap {
  210. return readFromCache(table) || addToCache(table, computeMap(table));
  211. }
  212. }
  213. // Compute a table map.
  214. function computeMap(table: Node): TableMap {
  215. if (table.type.spec.tableRole != 'table')
  216. throw new RangeError('Not a table node: ' + table.type.name);
  217. const width = findWidth(table),
  218. height = table.childCount;
  219. const map = [];
  220. let mapPos = 0;
  221. let problems: Problem[] | null = null;
  222. const colWidths: ColWidths = [];
  223. for (let i = 0, e = width * height; i < e; i++) map[i] = 0;
  224. for (let row = 0, pos = 0; row < height; row++) {
  225. const rowNode = table.child(row);
  226. pos++;
  227. for (let i = 0; ; i++) {
  228. while (mapPos < map.length && map[mapPos] != 0) mapPos++;
  229. if (i == rowNode.childCount) break;
  230. const cellNode = rowNode.child(i);
  231. const { colspan, rowspan, colwidth } = cellNode.attrs;
  232. for (let h = 0; h < rowspan; h++) {
  233. if (h + row >= height) {
  234. (problems || (problems = [])).push({
  235. type: 'overlong_rowspan',
  236. pos,
  237. n: rowspan - h,
  238. });
  239. break;
  240. }
  241. const start = mapPos + h * width;
  242. for (let w = 0; w < colspan; w++) {
  243. if (map[start + w] == 0) map[start + w] = pos;
  244. else
  245. (problems || (problems = [])).push({
  246. type: 'collision',
  247. row,
  248. pos,
  249. n: colspan - w,
  250. });
  251. const colW = colwidth && colwidth[w];
  252. if (colW) {
  253. const widthIndex = ((start + w) % width) * 2,
  254. prev = colWidths[widthIndex];
  255. if (
  256. prev == null ||
  257. (prev != colW && colWidths[widthIndex + 1] == 1)
  258. ) {
  259. colWidths[widthIndex] = colW;
  260. colWidths[widthIndex + 1] = 1;
  261. } else if (prev == colW) {
  262. colWidths[widthIndex + 1]++;
  263. }
  264. }
  265. }
  266. }
  267. mapPos += colspan;
  268. pos += cellNode.nodeSize;
  269. }
  270. const expectedPos = (row + 1) * width;
  271. let missing = 0;
  272. while (mapPos < expectedPos) if (map[mapPos++] == 0) missing++;
  273. if (missing)
  274. (problems || (problems = [])).push({ type: 'missing', row, n: missing });
  275. pos++;
  276. }
  277. const tableMap = new TableMap(width, height, map, problems);
  278. let badWidths = false;
  279. // For columns that have defined widths, but whose widths disagree
  280. // between rows, fix up the cells whose width doesn't match the
  281. // computed one.
  282. for (let i = 0; !badWidths && i < colWidths.length; i += 2)
  283. if (colWidths[i] != null && colWidths[i + 1] < height) badWidths = true;
  284. if (badWidths) findBadColWidths(tableMap, colWidths, table);
  285. return tableMap;
  286. }
  287. function findWidth(table: Node): number {
  288. let width = -1;
  289. let hasRowSpan = false;
  290. for (let row = 0; row < table.childCount; row++) {
  291. const rowNode = table.child(row);
  292. let rowWidth = 0;
  293. if (hasRowSpan)
  294. for (let j = 0; j < row; j++) {
  295. const prevRow = table.child(j);
  296. for (let i = 0; i < prevRow.childCount; i++) {
  297. const cell = prevRow.child(i);
  298. if (j + cell.attrs.rowspan > row) rowWidth += cell.attrs.colspan;
  299. }
  300. }
  301. for (let i = 0; i < rowNode.childCount; i++) {
  302. const cell = rowNode.child(i);
  303. rowWidth += cell.attrs.colspan;
  304. if (cell.attrs.rowspan > 1) hasRowSpan = true;
  305. }
  306. if (width == -1) width = rowWidth;
  307. else if (width != rowWidth) width = Math.max(width, rowWidth);
  308. }
  309. return width;
  310. }
  311. function findBadColWidths(
  312. map: TableMap,
  313. colWidths: ColWidths,
  314. table: Node,
  315. ): void {
  316. if (!map.problems) map.problems = [];
  317. const seen: Record<number, boolean> = {};
  318. for (let i = 0; i < map.map.length; i++) {
  319. const pos = map.map[i];
  320. if (seen[pos]) continue;
  321. seen[pos] = true;
  322. const node = table.nodeAt(pos);
  323. if (!node) {
  324. throw new RangeError(`No cell with offset ${pos} found`);
  325. }
  326. let updated = null;
  327. const attrs = node.attrs as CellAttrs;
  328. for (let j = 0; j < attrs.colspan; j++) {
  329. const col = (i + j) % map.width;
  330. const colWidth = colWidths[col * 2];
  331. if (
  332. colWidth != null &&
  333. (!attrs.colwidth || attrs.colwidth[j] != colWidth)
  334. )
  335. (updated || (updated = freshColWidth(attrs)))[j] = colWidth;
  336. }
  337. if (updated)
  338. map.problems.unshift({
  339. type: 'colwidth mismatch',
  340. pos,
  341. colwidth: updated,
  342. });
  343. }
  344. }
  345. function freshColWidth(attrs: Attrs): ColWidths {
  346. if (attrs.colwidth) return attrs.colwidth.slice();
  347. const result: ColWidths = [];
  348. for (let i = 0; i < attrs.colspan; i++) result.push(0);
  349. return result;
  350. }