Skip to content

Build your own AI office with Univer Office SDK. Bring editing, calculation, collaboration, and file processing into your product for people and AI agents. Built on an extensible open-source core.

26.3 KB
Raw Blame
/**
 * Copyright 2023-present DreamNum Co., Ltd.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import type { ITextRange } from '../../../sheets/typedef';
import type { ICustomRange, IDocumentBody } from '../../../types/interfaces/i-document-data';
import type { IDeleteAction, IInsertAction, IRetainAction, TextXAction } from './action-types';
import { UpdateDocsAttributeType } from '../../../shared/command-enum';
import { Tools } from '../../../shared/tools';
import { DataStreamTreeTokenType } from '../types';
import { ActionIterator } from './action-iterator';
import { PRESERVE_INSERTED_PARAGRAPH_IDS, TextXActionType } from './action-types';
import { textXApply } from './apply';
import {
    normalizeInsertedParagraphIdsForDocument,
    normalizeInsertedSectionIdsForDocument,
    RESTORE_INSERTED_PARAGRAPH_IDS,
} from './apply-utils/common';
import {
    appendRangeUpdates,
    composeRangeUpdate,
    dropRemovedRangeAnchors,
    getChangedPropertyPaths,
    getRangeUpdates,
    moveRangeUpdates,
    reconcileRangeUpdates,
    transformRangeUpdate,
    withoutRangeUpdates,
} from './custom-range-update';
import { transformBody } from './transform-utils';
import { composeBody, getBodySlice, getBodySliceForTextXAction, isUselessRetainAction } from './utils';

function onlyHasDataStream(body: IDocumentBody) {
    return Object.keys(body).length === 1;
}

function getValueRangeIds(actions: TextXAction[]): Set<string> {
    return new Set(actions.flatMap((action) => action.t !== TextXActionType.RETAIN && action.valueRangeId ? [action.valueRangeId] : []));
}

function withoutValueRangeMetadata(actions: TextXAction[], suppressed: Set<string>): TextXAction[] {
    return actions.map((action) => {
        if (!action.body?.customRanges?.some((range) => suppressed.has(range.rangeId))) {
            return action;
        }
        const body: IDocumentBody = { ...action.body, customRanges: action.body.customRanges.filter((range) => !suppressed.has(range.rangeId)) };
        if (!body.customRanges?.length) {
            delete body.customRanges;
        }
        return { ...action, body };
    });
}

function insertedAnchorPriority(first: TextXAction, second: TextXAction, priority: TPriority): boolean {
    if (first?.t !== TextXActionType.INSERT || second?.t !== TextXActionType.INSERT) {
        return priority === 'left';
    }
    const firstText = first.body.dataStream;
    const secondText = second.body.dataStream;
    if (firstText === secondText) {
        return priority === 'left';
    }
    // Restored delimiters enclose text typed at the collapsed boundary. Neither
    // side of a removed delimiter remains distinguishable as a text position.
    if (firstText === DataStreamTreeTokenType.CUSTOM_RANGE_START || secondText === DataStreamTreeTokenType.CUSTOM_RANGE_END) {
        return true;
    }
    if (firstText === DataStreamTreeTokenType.CUSTOM_RANGE_END || secondText === DataStreamTreeTokenType.CUSTOM_RANGE_START) {
        return false;
    }
    return priority === 'left';
}

function normalizeInsertActionParagraphIds(
    body: IDocumentBody,
    doc: IDocumentBody,
    currentIndex: number,
    reservedParagraphIds: Set<string>
) {
    normalizeInsertedParagraphIdsForDocument(doc.paragraphs, body.paragraphs, currentIndex, {
        freshenSplitParagraph: false,
        preserveExplicitParagraphIds: Boolean((body as IDocumentBody & Record<string, unknown>)[PRESERVE_INSERTED_PARAGRAPH_IDS]),
        reservedParagraphIds,
        dataStream: doc.dataStream,
    });
}

export type TPriority = 'left' | 'right';

export class TextX {
    // static name = 'text-x';

    static id = 'text-x';

    static uri = 'https://github.com/dream-num/univer#text-x';

    static apply(doc: IDocumentBody, actions: TextXAction[]): IDocumentBody {
        return textXApply(doc, actions);
    }

    // eslint-disable-next-line complexity
    static compose(thisActions: TextXAction[], otherActions: TextXAction[]): TextXAction[] {
        const thisUpdates = getRangeUpdates(thisActions);
        const otherUpdates = getRangeUpdates(otherActions);
        if (thisUpdates.length || otherUpdates.length) {
            const thisText = withoutRangeUpdates(thisActions);
            const otherText = withoutRangeUpdates(otherActions);
            const updates = new Map(moveRangeUpdates(thisUpdates, otherText).map((update) => [update.rangeId, update]));
            for (const update of otherUpdates) {
                updates.set(update.rangeId, composeRangeUpdate(updates.get(update.rangeId), update));
            }
            return appendRangeUpdates(TextX.compose(thisText, otherText), Array.from(updates.values()));
        }
        const thisIter = new ActionIterator(thisActions);
        const otherIter = new ActionIterator(otherActions);

        const textX = new TextX();

        while (thisIter.hasNext() || otherIter.hasNext()) {
            if (otherIter.peekType() === TextXActionType.INSERT) {
                textX.push(otherIter.next());
            } else if (thisIter.peekType() === TextXActionType.DELETE) {
                textX.push(thisIter.next());
            } else {
                const length = Math.min(thisIter.peekLength(), otherIter.peekLength());
                const thisAction = thisIter.next(length);
                const otherAction = otherIter.next(length);

                if (thisAction.t === TextXActionType.INSERT && otherAction.t === TextXActionType.RETAIN) {
                    if (otherAction.body == null) {
                        textX.push(thisAction);
                    } else {
                        textX.push({
                            ...thisAction,
                            body: composeBody(thisAction.body, otherAction.body, otherAction.coverType),
                        });
                    }
                } else if (thisAction.t === TextXActionType.RETAIN && otherAction.t === TextXActionType.RETAIN) {
                    if (thisAction.body == null && otherAction.body == null) {
                        textX.push(thisAction.len !== Number.POSITIVE_INFINITY ? thisAction : otherAction); // or otherAction
                    } else if (thisAction.body && otherAction.body) {
                        const coverType = thisAction.coverType === UpdateDocsAttributeType.REPLACE || otherAction.coverType === UpdateDocsAttributeType.REPLACE
                            ? UpdateDocsAttributeType.REPLACE
                            : UpdateDocsAttributeType.COVER;

                        textX.push({
                            ...thisAction,
                            t: TextXActionType.RETAIN,
                            coverType,
                            body: composeBody(thisAction.body, otherAction.body, otherAction.coverType),
                        });
                    } else {
                        textX.push(thisAction.body ? thisAction : otherAction);
                    }
                } else if (thisAction.t === TextXActionType.RETAIN && otherAction.t === TextXActionType.DELETE) {
                    textX.push(otherAction);
                } else if (thisAction.t === TextXActionType.INSERT && otherAction.t === TextXActionType.DELETE) {
                    // Nothing need to do, they are just cancel off.
                }
                // else {
                //     // I think exec will never go here.
                //     throw new Error('unknown compose case');
                // }
            }
        }

        textX.trimEndUselessRetainAction();

        return textX.serialize();
    }

    /**
     * |(this↓ \| other→) | **insert** | **retain** | **delete** |
     * | ---------------- | ---------- | ---------- | ---------- |
     * |    **insert**    |   Case 1   |   Case 2   |   Case 2   |
     * |    **retain**    |   Case 1   |   Case 5   |   Case 4   |
     * |    **delete**    |   Case 1   |   Case 3   |   Case 3   |
     *
     * Case 1: When the other action type is an insert operation,
     *         the insert operation is retained regardless of the type of action this action
     * Case 2: When this action type is an insert operation and the other action type is a
     *         non-insert operation, you need to retain the length of this action insert
     * Case 3: When this action is a delete operation, there are two scenarios:
     *      1) When other is a delete operation, since it is a delete operation, this has
     *         already been deleted, so the target does not need to be in delete, and it can
     *         be continued directly
     *      2) When other is the retain operation, although this action delete occurs first,
     *         the delete priority is higher, so the delete operation is retained, and the origin
     *         delete has been applied, so it is directly continued
     * Case 4: other is the delete operation, this is the retain operation, and the target delete operation
     *         is kept
     * Case 5: When both other and this are retain operations
     *      1) If the other body attribute does not exist, directly retain length
     *      2) If the other body property exists, then execute the TransformBody logic to override it
     */
    // priority - if true, this actions takes priority over other, that is, this actions are considered to happen "first".
    // thisActions is the target action.
    static transform(thisActions: TextXAction[], otherActions: TextXAction[], priority: TPriority = 'right'): TextXAction[] {
        const thisUpdates = getRangeUpdates(thisActions);
        const otherUpdates = getRangeUpdates(otherActions);
        if (thisUpdates.length || otherUpdates.length) {
            const thisText = withoutRangeUpdates(thisActions);
            const otherText = withoutRangeUpdates(otherActions);
            const otherAfterThis = TextX._transform(thisText, otherText, priority, true);
            const movedUpdates = moveRangeUpdates(thisUpdates, otherAfterThis, true);
            const updates = movedUpdates.flatMap((update) => transformRangeUpdate(
                update,
                otherUpdates.find((item) => item.rangeId === update.rangeId),
                priority
            ));
            const suppressed = movedUpdates.flatMap((update) => update.range &&
                otherUpdates.some((other) => other.rangeId === update.rangeId && !other.range)
                ? [update.range]
                : []);
            return dropRemovedRangeAnchors(
                reconcileRangeUpdates(TextX._transform(otherText, thisText, priority === 'left' ? 'right' : 'left', true), otherUpdates),
                suppressed,
                updates
            );
        }
        return this._transform(otherActions, thisActions, priority === 'left' ? 'right' : 'left');
    }

    // otherActions is the actions to be transformed.
    static _transform(thisActions: TextXAction[], otherActions: TextXAction[], priority: TPriority = 'right', rangeAnchorAffinity = false): TextXAction[] {
        const thisValues = getValueRangeIds(thisActions);
        const conflicts = new Set(Array.from(getValueRangeIds(otherActions)).filter((id) => thisValues.has(id)));
        const thisIter = new ActionIterator(conflicts.size && priority === 'right' ? withoutValueRangeMetadata(thisActions, conflicts) : thisActions);
        const otherIter = new ActionIterator(conflicts.size && priority === 'left' ? withoutValueRangeMetadata(otherActions, conflicts) : otherActions);

        const textX = new TextX();

        while (thisIter.hasNext() || otherIter.hasNext()) {
            if (
                thisIter.peekType() === TextXActionType.INSERT &&
                ((rangeAnchorAffinity ? insertedAnchorPriority(thisIter.peek(), otherIter.peek(), priority) : priority === 'left') || otherIter.peekType() !== TextXActionType.INSERT)
            ) {
                const thisAction = thisIter.next();
                if (thisAction.t === TextXActionType.INSERT && thisAction.valueRangeId && conflicts.has(thisAction.valueRangeId) && priority === 'right') {
                    textX.push({ t: TextXActionType.DELETE, len: thisAction.len, valueRangeId: thisAction.valueRangeId });
                } else {
                    textX.retain(thisAction.len);
                }
            } else if (otherIter.peekType() === TextXActionType.INSERT) {
                const otherAction = otherIter.next();
                if (otherAction.t !== TextXActionType.INSERT || !otherAction.valueRangeId || !conflicts.has(otherAction.valueRangeId) || priority !== 'left') {
                    textX.push(otherAction);
                }
            } else {
                const length = Math.min(thisIter.peekLength(), otherIter.peekLength());
                const thisAction = thisIter.next(length);
                const otherAction = otherIter.next(length);

                // handle this-delete case.
                if (thisAction.t === TextXActionType.DELETE) {
                    continue;
                }

                // handle other-delete case.
                if (otherAction.t === TextXActionType.DELETE) {
                    textX.push(otherAction);
                    continue;
                }

                // handle this-retain + other-retain case.
                if (thisAction.body == null || otherAction.body == null) {
                    textX.push(otherAction);
                } else {
                    const { coverType, body } = transformBody(thisAction as IRetainAction, otherAction as IRetainAction, priority === 'left');
                    textX.push({
                        ...otherAction,
                        t: TextXActionType.RETAIN,
                        coverType,
                        body,
                    });
                }
            }
        }

        textX.trimEndUselessRetainAction();

        return textX.serialize();
    }

    /**
     * Used to transform selection. Why not named transformSelection?
     * Because Univer Doc supports multiple Selections in one document, user need to encapsulate transformSelections at the application layer.
     */
    static transformPosition(thisActions: TextXAction[], index: number, priority = false): number {
        const thisIter = new ActionIterator(thisActions);

        let offset = 0;

        while (thisIter.hasNext() && offset <= index) {
            const length = thisIter.peekLength();
            const nextType = thisIter.peekType();
            thisIter.next();

            if (nextType === TextXActionType.DELETE) {
                index -= Math.min(length, index - offset);
                continue;
            } else if (nextType === TextXActionType.INSERT && (offset < index || !priority)) {
                index += length;
            }
            offset += length;
        }

        return index;
    }

    static isNoop(actions: TextXAction[]) {
        return actions.length === 0;
    }

    static invert(actions: TextXAction[]): TextXAction[] {
        if (getRangeUpdates(actions).length) {
            const restored = actions.flatMap((action) => {
                if (action.t !== TextXActionType.RETAIN || !action.rangeUpdates) {
                    return [];
                }
                if (!action.oldRangeUpdates) {
                    throw new Error('makeInvertible must capture custom ranges before inversion.');
                }
                return action.oldRangeUpdates;
            });
            return appendRangeUpdates(TextX.invert(withoutRangeUpdates(actions)), Tools.deepClone(restored));
        }
        const invertedActions: TextXAction[] = [];

        for (const action of actions) {
            if (action.t === TextXActionType.INSERT) {
                invertedActions.push({
                    t: TextXActionType.DELETE,
                    len: action.len,
                    body: action.body,
                    valueRangeId: action.valueRangeId,
                });
            } else if (action.t === TextXActionType.DELETE) {
                if (action.body == null) {
                    throw new Error('Can not invert DELETE action without body property, makeInvertible must be called first.');
                }

                if (action.body.paragraphs?.length) {
                    (action.body as IDocumentBody & Record<string, unknown>)[RESTORE_INSERTED_PARAGRAPH_IDS] = true;
                    Reflect.set(action.body, PRESERVE_INSERTED_PARAGRAPH_IDS, true);
                }

                invertedActions.push({
                    t: TextXActionType.INSERT,
                    body: action.body,
                    len: action.len,
                    valueRangeId: action.valueRangeId,
                });
            } else {
                if (action.body != null) {
                    if (action.oldBody == null) {
                        throw new Error('Can not invert RETAIN action without oldBody property, makeInvertible must be called first.');
                    }

                    invertedActions.push({
                        t: TextXActionType.RETAIN,
                        body: action.oldBody,
                        oldBody: action.body,
                        len: action.len,
                        coverType: UpdateDocsAttributeType.REPLACE,
                    });
                } else {
                    invertedActions.push(action);
                }
            }
        }

        return invertedActions;
    }

    static makeInvertible(actions: TextXAction[], doc: IDocumentBody): TextXAction[] {
        const invertibleActions: TextXAction[] = [];

        let index = 0;
        const reservedParagraphIds = new Set<string>();
        const reservedSectionIds = new Set<string>();

        for (const action of actions) {
            if (action.t === TextXActionType.RETAIN && action.rangeUpdates) {
                action.oldRangeUpdates = action.rangeUpdates.map(({ rangeId, propertyPaths }) => {
                    const index = doc.customRanges?.findIndex((range) => range.rangeId === rangeId) ?? -1;
                    return {
                        rangeId,
                        range: index < 0 ? null : Tools.deepClone(doc.customRanges![index]),
                        nextRangeId: index < 0 ? undefined : doc.customRanges![index + 1]?.rangeId ?? null,
                        propertyPaths: index < 0 ? undefined : propertyPaths,
                    };
                });
            }
            if (action.t === TextXActionType.INSERT) {
                normalizeInsertActionParagraphIds(action.body, doc, index, reservedParagraphIds);
                normalizeInsertedSectionIdsForDocument(doc.sectionBreaks, action.body.sectionBreaks, reservedSectionIds);
            }

            if (action.t === TextXActionType.DELETE && (action.body == null || (action.body && action.body.dataStream.length !== action.len))) {
                const body = getBodySliceForTextXAction(doc, index, index + action.len, false);
                action.len = body.dataStream.length;
                action.body = body;
            }

            if (action.t === TextXActionType.RETAIN && action.body != null) {
                const body = getBodySlice(doc, index, index + action.len, true);

                // Restoring untouched attributes can overwrite peer formatting or
                // reinsert clipped enclosing ranges. Paragraph identities need separate handling below.
                for (const field of Object.keys(body) as Array<keyof IDocumentBody>) {
                    if (field !== 'dataStream' && field !== 'paragraphs' && action.body[field] == null) {
                        Reflect.deleteProperty(body, field);
                    }
                }

                // Text-only formatting must not recreate paragraph identities on undo.
                if (action.body.paragraphs == null) {
                    delete body.paragraphs;
                } else {
                    const previousParagraphs = new Map(body.paragraphs?.map((paragraph) => [paragraph.startIndex, paragraph]));
                    action.body.paragraphs = action.body.paragraphs.map((paragraph) => {
                        const previous = previousParagraphs.get(paragraph.startIndex);
                        if (!previous || (paragraph.paragraphId != null && paragraph.paragraphId !== previous.paragraphId)) {
                            return paragraph;
                        }

                        // Unchanged identities are not formatting intent. Keeping them in
                        // either direction would overwrite a concurrent split's new id.
                        const formatting = { ...paragraph };
                        Reflect.deleteProperty(formatting, 'paragraphId');
                        Reflect.deleteProperty(previous, 'paragraphId');
                        return formatting;
                    });
                }

                action.oldBody = {
                    ...body,
                    dataStream: '',
                };
                action.len = body.dataStream.length;
            }

            invertibleActions.push(action);

            if (action.t !== TextXActionType.INSERT) {
                index += action.len;
            }
        }

        return invertibleActions;
    }

    private _actions: TextXAction[] = [];

    /** Edits only changed property leaves; does not replace range identity, bounds or peer properties. */
    updateCustomRangeProperties(range: ICustomRange, properties: NonNullable<ICustomRange['properties']>): this {
        const propertyPaths = getChangedPropertyPaths(range.properties ?? {}, properties);
        if (propertyPaths.length) {
            this.updateCustomRanges([{ rangeId: range.rangeId, range: { ...range, properties }, propertyPaths }]);
        }
        return this;
    }

    /** Updates identities after all text edits; range positions refer to the resulting document. */
    updateCustomRanges(updates: NonNullable<IRetainAction['rangeUpdates']>): this {
        this.push({ t: TextXActionType.RETAIN, len: 0, rangeUpdates: updates });
        return this;
    }

    insert(len: number, body: IDocumentBody): this {
        const insertAction: IInsertAction = {
            t: TextXActionType.INSERT,
            body,
            len,
        };

        this.push(insertAction);
        return this;
    }

    retain(len: number, body?: IDocumentBody, coverType?: UpdateDocsAttributeType): this {
        const retainAction: IRetainAction = {
            t: TextXActionType.RETAIN,
            len,
        };

        if (body != null) {
            retainAction.body = body;
        }

        if (coverType != null) {
            retainAction.coverType = coverType;
        }

        this.push(retainAction);

        return this;
    }

    delete(len: number): this {
        const deleteAction: IDeleteAction = {
            t: TextXActionType.DELETE,
            len,
        };

        this.push(deleteAction);

        return this;
    }

    empty(): this {
        this._actions = [];
        return this;
    }

    serialize(): TextXAction[] {
        return this._actions;
    }

    // eslint-disable-next-line complexity
    push(...args: TextXAction[]): this {
        if (args.length > 1) {
            for (const ac of args) {
                this.push(ac);
            }

            return this;
        }

        let index = this._actions.length;
        let lastAction = this._actions[index - 1];

        const newAction = Tools.deepClone(args[0]);

        // Nothing need to do, if the retain 0 and body is null.
        if (newAction.t === TextXActionType.RETAIN && newAction.len === 0 && newAction.body == null && !newAction.rangeUpdates) {
            return this;
        }

        if (typeof lastAction === 'object') {
            // if lastAction and newAction are both delete action, merge the two actions and return this.
            if (lastAction.t === TextXActionType.DELETE && newAction.t === TextXActionType.DELETE && lastAction.valueRangeId === newAction.valueRangeId) {
                lastAction.len += newAction.len;

                return this;
            }

            // Since it does not matter if we insert before or after deleting at the same index,
            // always prefer to insert first
            if (lastAction.t === TextXActionType.DELETE && newAction.t === TextXActionType.INSERT) {
                index -= 1;
                lastAction = this._actions[index - 1];

                if (lastAction == null) {
                    this._actions.unshift(newAction);

                    return this;
                }
            }

            // if lastAction and newAction are both retain action and has no body, merge the two actions and return this.
            if (lastAction.t === TextXActionType.RETAIN && newAction.t === TextXActionType.RETAIN && lastAction.body == null && newAction.body == null && !lastAction.rangeUpdates && !newAction.rangeUpdates) {
                lastAction.len += newAction.len;

                return this;
            }

            // Both are insert action, and has no styles, merge it.
            if (lastAction.t === TextXActionType.INSERT && onlyHasDataStream(lastAction.body) && newAction.t === TextXActionType.INSERT && onlyHasDataStream(newAction.body) && lastAction.valueRangeId === newAction.valueRangeId) {
                lastAction.len += newAction.len;
                lastAction.body.dataStream += newAction.body.dataStream;

                return this;
            }
        }

        if (index === this._actions.length) {
            this._actions.push(newAction);
        } else {
            this._actions.splice(index, 0, newAction);
        }

        return this;
    }

    protected trimEndUselessRetainAction(): this {
        let lastAction = this._actions[this._actions.length - 1];

        while (lastAction && lastAction.t === TextXActionType.RETAIN && isUselessRetainAction(lastAction)) {
            this._actions.pop();

            lastAction = this._actions[this._actions.length - 1];
        }

        return this;
    }
}

export type TextXSelection = TextX & {
    selections?: ITextRange[];
};

// FIXME: @Jocs, Use to avoid storybook error. and move the static name property to here.
Object.defineProperty(TextX, 'name', {
    value: 'text-x',
});