Skip to content

An open-source, privacy-first, self-hosted knowledge workspace where humans and AI agents work together 开源、隐私优先、自托管的知识工作空间,让人与智能体在此协作

17.9 KB
Raw Blame
// SiYuan - https://github.com/siyuan-note/siyuan
// Copyright (c) 2020-present, b3log.org
// SPDX-License-Identifier: AGPL-3.0-or-later

package model

import (
	"fmt"
	"maps"
	"regexp"
	"slices"
	"sync"
	"sync/atomic"
	"time"

	"github.com/88250/gulu"
	"github.com/88250/lute/ast"
	"github.com/88250/lute/parse"
	"github.com/siyuan-note/siyuan/kernel/treenode"
	"github.com/siyuan-note/siyuan/kernel/util"
)

// UndoEntry 是撤销栈中的一条记录。跨文档操作(MutatedRootIDs 含多个 rootID)的 entry
// 会以同一指针同时挂在这些 rootID 的栈上,撤销任一端时联动其他端移除引用。
type UndoEntry struct {
	id             string
	doOperations   []*Operation
	undoOperations []*Operation
	timestamp      int64
	mutatedRootIDs []string // 真正被写盘修改的树 rootID,联动与跨文档判定用
}

// DoOperationsForReplay 返回正向操作副本,供 redo 重放构造事务。
func (e *UndoEntry) DoOperationsForReplay() []*Operation {
	return cloneOperations(e.doOperations)
}

// UndoOperationsForReplay 返回逆向操作副本,供 undo 重放构造事务。
func (e *UndoEntry) UndoOperationsForReplay() []*Operation {
	return cloneOperations(e.undoOperations)
}

// MutatedRootIDs 返回该条目影响的 rootID 列表副本。
func (e *UndoEntry) MutatedRootIDs() []string {
	if nil == e.mutatedRootIDs {
		return nil
	}
	ret := make([]string, len(e.mutatedRootIDs))
	copy(ret, e.mutatedRootIDs)
	return ret
}

// undoStack 是单个 rootID 的撤销/重做栈。
type undoStack struct {
	undoStack []*UndoEntry
	redoStack []*UndoEntry
	hasUndo   bool // 复现前端 hasUndo 状态机:undo 后置 true,add 时若 true 则清 redo
}

// UndoLog 是全局撤销日志,按 rootID 分栈,所有窗口/客户端共享同一权威。
type UndoLog struct {
	mu     sync.Mutex
	stacks map[string]*undoStack
	max    int
}

// GlobalUndoLog 全局撤销日志单例。内存态,重启清空。
var GlobalUndoLog = newUndoLog(64)

var undoEntrySeq atomic.Uint64

func newUndoLog(max int) *UndoLog {
	return &UndoLog{
		stacks: map[string]*undoStack{},
		max:    max,
	}
}

func newUndoEntryID() string {
	seq := undoEntrySeq.Add(1)
	return fmt.Sprintf("undo-%d-%d", time.Now().UnixNano(), seq)
}

// stack 返回 rootID 对应的栈,不存在则返回 nil。
func (l *UndoLog) stack(rootID string) *undoStack {
	return l.stacks[rootID]
}

// stackOrCreate 返回 rootID 对应的栈,不存在则新建。
func (l *UndoLog) stackOrCreate(rootID string) *undoStack {
	s := l.stacks[rootID]
	if nil == s {
		s = &undoStack{}
		l.stacks[rootID] = s
	}
	return s
}

// Record 记录一笔已提交的编辑器事务。仅当事务来自 /api/transactions(fromAPI)、
// 携带非空 UndoOperations、且非 undo/redo 重放(isReplay)时记录。
func (l *UndoLog) Record(tx *Transaction) {
	if !tx.fromAPI || 0 == len(tx.UndoOperations) || tx.isReplay {
		return
	}

	rootIDs := tx.GetMutatedRootIDs()
	if 0 == len(rootIDs) {
		// 纯属性视图单元格编辑等不写 block tree 的事务不入栈
		return
	}

	l.mu.Lock()
	defer l.mu.Unlock()

	entry := &UndoEntry{
		id:             newUndoEntryID(),
		doOperations:   cloneOperations(tx.DoOperations),
		undoOperations: cloneOperations(tx.UndoOperations),
		timestamp:      time.Now().UnixMilli(),
		mutatedRootIDs: rootIDs,
	}

	for _, rootID := range rootIDs {
		s := l.stackOrCreate(rootID)
		s.undoStack = append(s.undoStack, entry)
		if s.hasUndo {
			s.redoStack = nil
			s.hasUndo = false
		}
		if l.max < len(s.undoStack) {
			s.undoStack = s.undoStack[len(s.undoStack)-l.max:]
		}
	}
}

// Peek 返回 rootID 撤销栈顶(不弹出),栈空返回 nil。
func (l *UndoLog) Peek(rootID string) *UndoEntry {
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s || 0 == len(s.undoStack) {
		return nil
	}
	return s.undoStack[len(s.undoStack)-1]
}

// Undo 弹出 rootID 撤销栈顶,压入执行栈重做栈,置 hasUndo。仅动执行栈,不做联动移除。
// 成功执行逆操作后调 UndoCommit 完成联动;失败调 UndoRollback 精确回滚(因只动了执行栈)。
// 返回弹出的 entry;栈空返回 nil。
func (l *UndoLog) Undo(rootID string) *UndoEntry {
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s || 0 == len(s.undoStack) {
		return nil
	}

	entry := s.undoStack[len(s.undoStack)-1]
	s.undoStack = s.undoStack[:len(s.undoStack)-1]
	// 只压入执行撤销的栈,符合语义 B:在 B 按 Ctrl+Y 不重做这条
	s.redoStack = append(s.redoStack, entry)
	if l.max < len(s.redoStack) {
		s.redoStack = s.redoStack[len(s.redoStack)-l.max:]
	}
	s.hasUndo = true
	return entry
}

// UndoCommit 在逆操作成功执行后,联动从其他关联栈移除该 entry(按 id 匹配)。
func (l *UndoLog) UndoCommit(entry *UndoEntry, rootID string) {
	if nil == entry {
		return
	}
	l.mu.Lock()
	defer l.mu.Unlock()

	for _, r := range entry.mutatedRootIDs {
		if r == rootID {
			continue
		}
		l.removeEntry(r, entry.id)
	}
}

// UndoRollback 在逆操作执行失败时回滚执行栈:把 entry 从重做栈移回撤销栈顶,复位 hasUndo。
// 因 Undo 只动了执行栈,此回滚精确无误。
func (l *UndoLog) UndoRollback(entry *UndoEntry, rootID string) {
	if nil == entry {
		return
	}
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s {
		return
	}
	// 从执行栈重做栈顶移除 entry(Undo 压入的)
	if 0 < len(s.redoStack) && s.redoStack[len(s.redoStack)-1].id == entry.id {
		s.redoStack = s.redoStack[:len(s.redoStack)-1]
	}
	// 推回执行栈撤销栈顶(恢复 Undo 弹出前的位置)
	s.undoStack = append(s.undoStack, entry)
	s.hasUndo = false
}

// Redo 弹出 rootID 重做栈顶,压回执行栈撤销栈。仅动执行栈,不做联动重挂。
// 不改 hasUndo(复现前端 redo 的不对称)。成功后调 RedoCommit;失败调 RedoRollback。
func (l *UndoLog) Redo(rootID string) *UndoEntry {
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s || 0 == len(s.redoStack) {
		return nil
	}

	entry := s.redoStack[len(s.redoStack)-1]
	s.redoStack = s.redoStack[:len(s.redoStack)-1]
	s.undoStack = append(s.undoStack, entry)
	return entry
}

// RedoCommit 在重做成功执行后,联动把 entry 重新挂到其他关联栈顶。
func (l *UndoLog) RedoCommit(entry *UndoEntry, rootID string) {
	if nil == entry {
		return
	}
	l.mu.Lock()
	defer l.mu.Unlock()

	for _, r := range entry.mutatedRootIDs {
		if r == rootID {
			continue
		}
		rs := l.stackOrCreate(r)
		rs.undoStack = append(rs.undoStack, entry)
		if l.max < len(rs.undoStack) {
			rs.undoStack = rs.undoStack[len(rs.undoStack)-l.max:]
		}
	}
}

// RedoRollback 在重做执行失败时回滚执行栈:把 entry 从撤销栈移回重做栈顶。
// 因 Redo 只动了执行栈,此回滚精确无误。
func (l *UndoLog) RedoRollback(entry *UndoEntry, rootID string) {
	if nil == entry {
		return
	}
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s {
		return
	}
	// 从执行栈撤销栈顶移除 entry(Redo 压入的)
	if 0 < len(s.undoStack) && s.undoStack[len(s.undoStack)-1].id == entry.id {
		s.undoStack = s.undoStack[:len(s.undoStack)-1]
	}
	// 推回执行栈重做栈顶
	s.redoStack = append(s.redoStack, entry)
	if l.max < len(s.redoStack) {
		s.redoStack = s.redoStack[len(s.redoStack)-l.max:]
	}
}

// State 返回 rootID 的撤销/重做可用性及栈顶关联的 mutatedRootIDs。
func (l *UndoLog) State(rootID string) (canUndo, canRedo bool, peekMutatedRootIDs []string) {
	l.mu.Lock()
	defer l.mu.Unlock()

	s := l.stack(rootID)
	if nil == s {
		return
	}
	canUndo = 0 < len(s.undoStack)
	canRedo = 0 < len(s.redoStack)
	if canUndo {
		top := s.undoStack[len(s.undoStack)-1]
		peekMutatedRootIDs = append(peekMutatedRootIDs, top.mutatedRootIDs...)
		peekMutatedRootIDs = gulu.Str.RemoveDuplicatedElem(peekMutatedRootIDs)
	}
	return
}

// Clear 清理撤销日志。rootID 非空时清该文档栈并联动移除其他栈中相关条目;为空时清空全部。
func (l *UndoLog) Clear(rootID string) {
	l.clear(rootID)
}

// 返回状态发生变化的文档,包括联动移除跨文档记录的其他文档。
func (l *UndoLog) clear(rootID string) (rootIDs []string) {
	l.mu.Lock()
	defer l.mu.Unlock()

	if "" == rootID {
		for id := range l.stacks {
			rootIDs = append(rootIDs, id)
		}
		l.stacks = map[string]*undoStack{}
		return
	}
	rootIDs = append(rootIDs, rootID)

	s := l.stacks[rootID]
	if nil == s {
		return
	}
	// 收集该栈中所有跨文档条目的 id,联动从其他栈移除
	linkedIDs := map[string]bool{}
	for _, e := range s.undoStack {
		for _, r := range e.mutatedRootIDs {
			if r != rootID {
				linkedIDs[e.id] = true
			}
		}
	}
	for _, e := range s.redoStack {
		for _, r := range e.mutatedRootIDs {
			if r != rootID {
				linkedIDs[e.id] = true
			}
		}
	}
	delete(l.stacks, rootID)
	for otherID, other := range l.stacks {
		beforeUndo, beforeRedo := len(other.undoStack), len(other.redoStack)
		for id := range linkedIDs {
			other.undoStack = removeEntryByID(other.undoStack, id)
			other.redoStack = removeEntryByID(other.redoStack, id)
		}
		if beforeUndo != len(other.undoStack) || beforeRedo != len(other.redoStack) {
			rootIDs = append(rootIDs, otherID)
		}
	}
	return
}

// 非编辑器写盘成功后失效旧记录,并通知所有客户端更新撤销和重做状态。
func invalidateDocumentHistory(rootID string) {
	rootIDs := GlobalUndoLog.clear(rootID)
	states := map[string]map[string]bool{}
	for _, id := range rootIDs {
		canUndo, canRedo, _ := GlobalUndoLog.State(id)
		states[id] = map[string]bool{"canUndo": canUndo, "canRedo": canRedo}
	}
	event := util.NewCmdResult("transactions", 0, util.PushModeBroadcast)
	event.Data = []*Transaction{}
	event.Context = map[string]any{"rootIDs": rootIDs, "undoState": states}
	util.PushEvent(event)
}

// ClearAttributeView 从各文档栈清理涉及指定数据库的整笔撤销、重做记录,保留无关记录。
// 非编辑器事务移除绑定条目后,旧记录不能再安全地重放单元格编辑或数据库快照。
func (l *UndoLog) ClearAttributeView(avID string) {
	if avID == "" {
		return
	}
	l.mu.Lock()
	defer l.mu.Unlock()

	affected := func(entry *UndoEntry) bool {
		for _, operations := range [][]*Operation{entry.doOperations, entry.undoOperations} {
			for _, operation := range operations {
				if operation.AvID == avID {
					return true
				}
				if conversion := operation.listConversion; conversion != nil {
					for _, binding := range conversion.bindings {
						if binding.avID == avID {
							return true
						}
					}
				}
				if snapshot := operation.attributeViewFields; snapshot != nil && snapshot.changes[avID] != nil {
					return true
				}
				if items := operation.attributeViewItems; items != nil && items.relatedChanges != nil &&
					items.relatedChanges.changes[avID] != nil {
					return true
				}
			}
		}
		return false
	}
	for _, stack := range l.stacks {
		stack.undoStack = slices.DeleteFunc(stack.undoStack, affected)
		stack.redoStack = slices.DeleteFunc(stack.redoStack, affected)
	}
}

// removeEntry 从 rootID 栈中按 id 移除一条 entry(撤销联动用)。
func (l *UndoLog) removeEntry(rootID, id string) {
	s := l.stacks[rootID]
	if nil == s {
		return
	}
	s.undoStack = removeEntryByID(s.undoStack, id)
}

func removeEntryByID(stack []*UndoEntry, id string) []*UndoEntry {
	for i, e := range stack {
		if e.id == id {
			return append(stack[:i], stack[i+1:]...)
		}
	}
	return stack
}

// cloneOperations 复制操作及重放期间可能改写的引用字段,使日志条目与后续事务解耦。
// Data(any) 共享引用,事务执行只会替换 Data 本身,不会修改其内部内容。
func cloneOperations(ops []*Operation) []*Operation {
	if nil == ops {
		return nil
	}
	ret := make([]*Operation, len(ops))
	for i, op := range ops {
		cloned := *op
		cloned.BlockIDs = cloneOperationBlockIDs(op.BlockIDs)
		if nil != op.Context {
			cloned.Context = make(map[string]any, len(op.Context))
			maps.Copy(cloned.Context, op.Context)
		}
		ret[i] = &cloned
	}
	return ret
}

var dataNodeIDPattern = regexp.MustCompile(`data-node-id="([^"]+)"`)
var refcountAttrPattern = regexp.MustCompile(`\s*refcount="[^"]*"`)
var refcountDivPattern = regexp.MustCompile(`<div class="protyle-attr--refcount[^"]*"[^>]*>.*?</div>`)

func replaceReplayOperationID(operation *Operation, replacements map[string]string) (replaced bool) {
	newID, replaced := replacements[operation.ID]
	if !replaced {
		return false
	}
	// insert 恢复的容器 ID 换新后,紧随其后的 update 也必须指向新容器;delete 仍保留旧 ID 以清理冲突块。
	if "insert" == operation.Action || "update" == operation.Action {
		operation.ID = newID
	}
	return true
}

func replayOperationBlockIndexes(operations []*Operation) (insertIndexes, deleteIndexes map[string]int) {
	insertIndexes, deleteIndexes = map[string]int{}, map[string]int{}
	recordFirstIndex := func(indexes map[string]int, id string, index int) {
		if !ast.IsNodeIDPattern(id) {
			return
		}
		if _, exists := indexes[id]; !exists {
			indexes[id] = index
		}
	}
	for index, operation := range operations {
		switch operation.Action {
		case "delete":
			recordFirstIndex(deleteIndexes, operation.ID, index)
		case "insert":
			recordFirstIndex(insertIndexes, operation.ID, index)
			data, ok := operation.Data.(string)
			if !ok {
				continue
			}
			for _, match := range dataNodeIDPattern.FindAllStringSubmatch(data, -1) {
				recordFirstIndex(insertIndexes, match[1], index)
			}
		}
	}
	return
}

func replayBlockIDConflicts(node *ast.Node, insertIndex int, deleteIndexes map[string]int) bool {
	for current := node; nil != current; current = current.Parent {
		if deleteIndex, exists := deleteIndexes[current.ID]; exists && deleteIndex < insertIndex {
			return false
		}
	}
	return true
}

func existingReplayBlockIDs(insertIndexes, deleteIndexes map[string]int) map[string]bool {
	ret := map[string]bool{}
	ids := make([]string, 0, len(insertIndexes))
	for id := range insertIndexes {
		ids = append(ids, id)
	}
	blockTrees := treenode.GetBlockTrees(ids)
	loadedTrees := map[string]*parse.Tree{}
	loadFailed := map[string]bool{}
	for _, id := range ids {
		ret[id] = false
		blockTree := blockTrees[id]
		if nil == blockTree {
			continue
		}
		key := blockTree.BoxID + "\x00" + blockTree.Path
		tree, loaded := loadedTrees[key]
		if !loaded && !loadFailed[key] {
			var err error
			tree, err = loadTreeByBlockTree(blockTree)
			if nil != err || nil == tree {
				// 无法读取时按存在处理,避免在不确定状态下引入重复 ID。
				loadFailed[key] = true
			} else {
				loadedTrees[key] = tree
			}
		}
		if loadFailed[key] {
			ret[id] = true
			continue
		}
		node := treenode.GetNodeInTree(tree, id)
		ret[id] = nil != node && replayBlockIDConflicts(node, insertIndexes[id], deleteIndexes)
	}
	return ret
}

// ResolveReplayDuplicateIds 在 undo/redo 重放事务前解决块 ID 冲突。
// 场景:剪切块 X 后粘贴到别处(保留原 ID),再撤销剪切会 insert X,而 X 已存在于粘贴处,产生重复 ID。
// 这里检查实际重放的 insert 操作;若其引入的 ID 在块树中已存在,且不会被前置 delete 清理,
// 则在当前重放操作的 ID、ParentID、PreviousID、NextID、BlockIDs 与 Data 内联 ID 中统一替换为新 ID。
func ResolveReplayDuplicateIds(tx *Transaction) {
	if nil == tx || !tx.isReplay {
		return
	}

	insertIndexes, deleteIndexes := replayOperationBlockIndexes(tx.DoOperations)
	// 注意:只检测 DoOperations(实际执行的操作),不检测 UndoOperations。
	// UndoOperations 在 redo 时会作为新的 DoOperations 再次过 ResolveReplayDuplicateIds。
	// 若 undo 时也检测 UndoOperations 的 insert,会把 redo 用的 ID 换新,
	// 污染 DoOperations 的对应 delete(do/undo 共享 replacements),导致撤销删除错误 ID。
	if 0 == len(insertIndexes) {
		return
	}

	// blocktree 索引异步更新,立即撤销时可能仍残留已删除容器的记录,必须以当前 .sy 树为准。
	exist := existingReplayBlockIDs(insertIndexes, deleteIndexes)

	// 已存在的 ID 生成替换
	replacements := map[string]string{}
	for id, exists := range exist {
		if exists {
			replacements[id] = ast.NewNodeID()
		}
	}
	if 0 == len(replacements) {
		return
	}

	// 对实际重放的操作统一替换 ID 及关联字段
	apply := func(ops []*Operation) {
		for _, op := range ops {
			// 记录本操作的 ID 是否被换新,以便清除引用角标。
			idReplaced := replaceReplayOperationID(op, replacements)
			// delete 操作声明的 ID 是待删除的旧块本身,若换为新 ID,
			// doDelete 会找不到节点而静默跳过,导致旧块残留并在重放后产生重复块。
			// 典型场景:列表转段落后撤销——undo 先 delete 扁平化出的子块,再 insert 原列表
			// (HTML 内联同一批子块 ID),这些子块会被前置 delete 清理,本不该参与冲突替换。
			// https://github.com/siyuan-note/siyuan/issues/18012
			if newID, ok := replacements[op.ParentID]; ok {
				op.ParentID = newID
			}
			if newID, ok := replacements[op.PreviousID]; ok {
				op.PreviousID = newID
			}
			if newID, ok := replacements[op.NextID]; ok {
				op.NextID = newID
			}
			for i, blockID := range op.BlockIDs {
				if newID, ok := replacements[blockID]; ok {
					op.BlockIDs[i] = newID
				}
			}
			data, ok := op.Data.(string)
			if !ok {
				continue
			}
			for oldID, newID := range replacements {
				data = dataNodeIDPattern.ReplaceAllStringFunc(data, func(match string) string {
					if sub := dataNodeIDPattern.FindStringSubmatch(match); len(sub) > 1 && sub[1] == oldID {
						return `data-node-id="` + newID + `"`
					}
					return match
				})
			}
			// ID 被换新的块(剪切粘贴后撤销恢复的副本)清除引用角标,避免显示旧的 refcount。
			// 角标由 kernel 异步刷新(refreshRefCount)重建为正确值。
			if idReplaced {
				data = refcountDivPattern.ReplaceAllString(data, "")
				data = refcountAttrPattern.ReplaceAllString(data, "")
			}
			op.Data = data
		}
	}
	apply(tx.DoOperations)
}