mathtool2/lib/expr_node.dart

/// 结构化表达式模型 —— 计算器的输入不再是字符串，而是一棵树。
///
/// 为什么值得单独做一套：纯文本光标表达不了多参数结构。用户按了 `∫` 之后
/// 光标该放哪？按 `^` 之后指数该往哪写？用字符串只能靠"插入 `Integrate[, x]`
/// 再把光标往回退 4 位"这种把戏，模板一复杂就散架，分数、上下标更是没法表达。
/// 树 + 槽就没有这个问题。
///
/// 分工：**计算器用这套结构化输入，控制台继续用纯文本**（长表达式、粘贴、
/// 脚本式输入还是文本方便）。两者序列化后交给同一个求值内核。
library;

import 'package:meta/meta.dart';

/// 表达式节点。
sealed class ExprNode {
  const ExprNode();
}

/// 字面量：数字、变量名、常量。用字符串存，因为 `3.14`、`x`、`Pi` 都是文本。
class LitNode extends ExprNode {
  final String text;
  const LitNode(this.text);
}

/// 函数调用：`name[arg0, arg1, …]`。每个参数是一个槽。
class FuncNode extends ExprNode {
  final String name;
  final List<SeqNode> args;
  FuncNode(this.name, this.args);
}

/// 分式：分子 / 分母。
class FracNode extends ExprNode {
  SeqNode num;
  SeqNode den;
  FracNode({required this.num, required this.den});
}

/// 幂：底 ^ 指数。
class PowNode extends ExprNode {
  SeqNode base;
  SeqNode exp;
  PowNode({required this.base, required this.exp});
}

/// 括号分组 `( … )`。
///
/// 用独立节点而不是把括号当字面量：括号必须成对且包住一整段，
/// 当字面量的话用户能删掉半个括号，表达式就废了。
class GroupNode extends ExprNode {
  SeqNode inner;
  GroupNode(this.inner);
}

/// 花括号列表 `{ … }`。
///
/// 计算器自己不用它（Sum 的迭代范围是一个字面量），但**粘贴**进来的表达式
/// 可能带花括号（`Sum[f, {n, 1, Infinity}]`），没有这个节点就解析不了。
class BraceNode extends ExprNode {
  SeqNode inner;
  BraceNode(this.inner);
}

/// 大运算符：∫ / ∑ / ∏ / lim。
///
/// 为什么要单独一个节点，而不是复用 `FuncNode` + `{x,a,b}` 那种写法：
/// 上下限得单独成槽才画得到**习惯位置**（积分号的上方/下方、Σ 的上下、
/// lim 的下方）。塞在一个花括号字面量里就只能顺着排，画不出来。
///
/// 和 Symja 的对应关系（序列化时还原）：
///   Integrate[body, {variable, lower, upper}]   定积分；上下限都空时退化成不定积分
///   Sum[body, {variable, lower, upper}]         求和
///   Product[body, {variable, lower, upper}]     连乘
///   Limit[body, variable -> lower]              极限（upper 不用）
class BigOpNode extends ExprNode {
  /// 'Integrate' | 'Sum' | 'Product' | 'Limit'
  final String kind;

  /// 被积函数 / 求和项 / 取极限的表达式。
  SeqNode body;

  /// 积分变量 / 求和指标 / 趋近的变量。
  SeqNode variable;

  /// 下限：积分下限、求和起点、Limit 的趋近值。
  SeqNode lower;

  /// 上限。Limit 不用，留空槽且不显示。
  SeqNode upper;

  BigOpNode({
    required this.kind,
    required this.body,
    required this.variable,
    required this.lower,
    required this.upper,
  });

  bool get needsUpper => kind != 'Limit';
  bool get isDefinite => !lower.isEmpty || (needsUpper && !upper.isEmpty);
}

/// 后缀运算符，目前只有阶乘 `!`。
class PostfixNode extends ExprNode {
  SeqNode operand;
  final String op;
  PostfixNode({required this.operand, this.op = '!'});
}

/// 一个槽 = 一串节点。分式的分子分母、函数的参数、幂的指数都是槽。
class SeqNode {
  final List<ExprNode> children;
  SeqNode([List<ExprNode>? children]) : children = children ?? <ExprNode>[];

  bool get isEmpty => children.isEmpty;
}

/// 光标路径里的一跳：进入第 [child] 个孩子的第 [slot] 个槽。
class SlotStep {
  final int child;
  final int slot;
  const SlotStep(this.child, this.slot);
}

/// 光标位置。空路径 = 根槽；[offset] 是在最终那个槽里的插入位置。
class SlotPath {
  final List<SlotStep> steps;
  final int offset;

  const SlotPath(this.steps, this.offset);

  static const root = SlotPath(<SlotStep>[], 0);

  SlotPath push(int child, int slot) =>
      SlotPath([...steps, SlotStep(child, slot)], 0);

  /// 是否落在**同一个槽**里（只比路径，不比槽内位置）。
  ///
  /// 这个方法和 [operator ==] 的区别很关键：`offset` 是**槽内的插入位置**，
  /// 不属于"槽的身份"。渲染时判断"这个槽是不是光标所在的槽"必须用它 ——
  /// 早先用 `==` 比整个 SlotPath，而路径自带的 offset 恒为 0，
  /// 结果只有光标停在槽首时才认为聚焦，**打第一个字符光标就消失了**。
  bool sameSlotAs(SlotPath other) {
    if (other.steps.length != steps.length) return false;
    for (var i = 0; i < steps.length; i++) {
      if (steps[i].child != other.steps[i].child) return false;
      if (steps[i].slot != other.steps[i].slot) return false;
    }
    return true;
  }

  /// 回到父槽，并把光标停在刚才那个孩子之后。
  SlotPath? get parent {
    if (steps.isEmpty) return null;
    final last = steps.last;
    return SlotPath(steps.sublist(0, steps.length - 1), last.child + 1);
  }

  @override
  bool operator ==(Object other) {
    if (other is! SlotPath || other.offset != offset) return false;
    if (other.steps.length != steps.length) return false;
    for (var i = 0; i < steps.length; i++) {
      if (steps[i].child != other.steps[i].child) return false;
      if (steps[i].slot != other.steps[i].slot) return false;
    }
    return true;
  }

  @override
  int get hashCode =>
      Object.hash(offset, Object.hashAll(steps.map((s) => Object.hash(s.child, s.slot))));
}

/// 把一个槽序列化成 Symja 表达式。
///
/// 序列化不依赖任何文档状态，所以给出这个顶层入口，
/// 免得为了转个字符串还要 new 一个 ExprDoc。
String symjaOf(SeqNode seq) => ExprDoc().serializeSeq(seq);

/// 选区：**同一个槽里**一段连续的子节点。
///
/// 不做跨槽的任意范围 —— 那要处理"从分子选到分母"这种语义模糊的情况，
/// 而实际用起来，想剪切的东西几乎总在同一层（`2x+1` 就是根槽里连续的四个节点）。
@immutable
class SlotRange {
  final SlotPath path;
  final int start; // 含
  final int end; // 不含
  const SlotRange(this.path, this.start, this.end);

  bool get isEmpty => end <= start;

  @override
  bool operator ==(Object other) =>
      other is SlotRange && other.path == path && other.start == start && other.end == end;

  @override
  int get hashCode => Object.hash(path, start, end);
}

/// 编辑器文档：持有一棵树和一个光标，并实现所有编辑操作。
///
/// 可变对象，调用方自己 setState。刻意不做成 ChangeNotifier —— 操作很密集
/// （每敲一个键一次），让页面统一刷新比分发通知更简单也更快。
class ExprDoc {
  final SeqNode root = SeqNode();
  SlotPath cursor = SlotPath.root;

  /// 当前选区。null = 没选中（此时操作都作用在光标处）。
  SlotRange? selection;

  // ------------------------------------------------------------------ 选区

  void selectNodeAt(SlotPath path, int index) {
    selection = SlotRange(path, index, index + 1);
  }

  /// 把选区扩展到包含第 [index] 个节点（按住不放再点另一个节点的语义）。
  /// 只支持同一个槽内，跨槽忽略。
  void extendSelectionTo(SlotPath path, int index) {
    final s = selection;
    if (s == null || !s.path.sameSlotAs(path)) return;
    selection = SlotRange(
      s.path,
      index < s.start ? index : s.start,
      index + 1 > s.end ? index + 1 : s.end,
    );
  }

  void clearSelection() => selection = null;

  /// 选中的节点（按原位序）。
  List<ExprNode> get selectedNodes {
    final s = selection;
    if (s == null || s.isEmpty) return const <ExprNode>[];
    final children = slotAt(s.path).children;
    final from = s.start.clamp(0, children.length);
    final to = s.end.clamp(0, children.length);
    return children.sublist(from, to);
  }

  /// 选区的 Symja 文本（复制到剪贴板的内容）。
  String get selectionText => symjaOf(SeqNode(selectedNodes));

  /// 删掉选区，光标落到选区起点。
  void deleteSelection() {
    final s = selection;
    if (s == null || s.isEmpty) return;
    final children = slotAt(s.path).children;
    final from = s.start.clamp(0, children.length);
    final to = s.end.clamp(0, children.length);
    children.removeRange(from, to);
    cursor = SlotPath(s.path.steps, from);
    selection = null;
  }

  /// 在光标处插入一串节点（粘贴用），插完光标落在它们之后。
  void insertNodesAtCursor(List<ExprNode> nodes) {
    if (nodes.isEmpty) return;
    final seq = current;
    final at = cursor.offset.clamp(0, seq.children.length);
    seq.children.insertAll(at, nodes);
    cursor = SlotPath(cursor.steps, at + nodes.length);
    selection = null;
  }

  // ------------------------------------------------------------------ 取槽

  /// 按路径找到对应的槽。路径失效时返回根槽。
  SeqNode slotAt(SlotPath path) {
    var seq = root;
    for (final step in path.steps) {
      if (step.child < 0 || step.child >= seq.children.length) return root;
      final node = seq.children[step.child];
      final slots = _slotsOf(node);
      if (step.slot < 0 || step.slot >= slots.length) return seq;
      seq = slots[step.slot];
    }
    return seq;
  }

  static List<SeqNode> _slotsOf(ExprNode node) => switch (node) {
        FuncNode f => f.args,
        FracNode f => [f.num, f.den], // 0=分子 1=分母
        PowNode p => [p.base, p.exp], // 0=底 1=指数
        GroupNode g => [g.inner],
        BraceNode b => [b.inner],
        BigOpNode b => [b.body, b.variable, b.lower, b.upper],
        PostfixNode p => [p.operand],
        LitNode _ => const <SeqNode>[],
      };

  SeqNode get current => slotAt(cursor);

  // ------------------------------------------------------------------ 插入

  /// 在当前光标处插入一个节点；[enterSlot] 不为空则顺便把光标移进它的某个槽。
  void insert(ExprNode node, {int? enterSlot}) {
    final seq = current;
    final at = cursor.offset.clamp(0, seq.children.length);
    seq.children.insert(at, node);
    cursor = enterSlot == null
        ? SlotPath(cursor.steps, at + 1)
        : _descend(cursor, at, enterSlot);
  }

  SlotPath _descend(SlotPath from, int child, int slot) =>
      from.push(child, slot);

  /// 插入一个字符。
  ///
  /// 数字和小数点会**并进左边那个数字字面量**，而不是各建一个节点 ——
  /// 否则 `42` 是两个节点，退格只删最后一位、显示上还分不出是一个数还是两个。
  void insertChar(String ch) {
    final seq = current;
    if (cursor.offset > 0 && seq.children.isNotEmpty) {
      final left = seq.children[cursor.offset - 1];
      if (left is LitNode && _isNumberText(left.text) && _isNumberChar(ch)) {
        seq.children[cursor.offset - 1] = LitNode(left.text + ch);
        return;
      }
    }
    insert(LitNode(ch));
  }

  static bool _isNumberText(String s) =>
      s.isNotEmpty && RegExp(r'^[0-9.]+$').hasMatch(s);

  static bool _isNumberChar(String c) => RegExp(r'^[0-9.]$').hasMatch(c);

  /// 造一个大运算符。光标落在 body 槽（要填的那个）。
  void makeBigOp(String kind, {String variable = 'x', String lower = '',
      String upper = ''}) {
    SeqNode lit(String t) => t.isEmpty ? SeqNode() : SeqNode([LitNode(t)]);
    insert(
      BigOpNode(
        kind: kind,
        body: SeqNode(),
        variable: lit(variable),
        lower: lit(lower),
        upper: lit(upper),
      ),
      enterSlot: 0,
    );
  }

  /// 插入一对括号（光标停在里面）。
  void makeGroup() => insert(GroupNode(SeqNode()), enterSlot: 0);

  /// 把当前槽里光标左边那个节点取出来（没有则返回 null），并把它从槽里摘掉。
  ///
  /// `^`、`/`、`√` 这些"把前面那个东西变成结构的一部分"的操作靠它实现 ——
  /// 这是结构化编辑器和纯文本手感最接近的地方：先打 `x` 再按 `^`，就成了 x 的幂。
  ExprNode? takeLeft() {
    final seq = current;
    if (cursor.offset <= 0 || cursor.offset > seq.children.length) return null;
    cursor = SlotPath(cursor.steps, cursor.offset - 1);
    return seq.children.removeAt(cursor.offset);
  }

  /// 制造一个幂：底 = 光标左边那个节点（没有就用空底），光标落到指数上。
  void makePower() {
    final base = takeLeft();
    final node = PowNode(base: SeqNode(base == null ? null : [base]), exp: SeqNode());
    insert(node, enterSlot: 1);
  }

  /// 制造一个分式：分子 = 光标左边那个节点（没有就空着），光标落到分母上。
  void makeFraction() {
    final num = takeLeft();
    final node = FracNode(num: SeqNode(num == null ? null : [num]), den: SeqNode());
    insert(node, enterSlot: 1);
  }

  /// 制造一个函数调用，光标落在第一个参数槽。
  ///
  /// [prefill] 每一项对应一个参数：[String] 为空表示**留一个空槽给用户填**，
  /// 非空则预置成字面量（例如 `Sum` 的 `{n, 1, Infinity}`）。
  void makeFunction(String name, {List<String> prefill = const []}) {
    insert(
      FuncNode(name, [
        for (final p in prefill)
          p.isEmpty ? SeqNode() : SeqNode([LitNode(p)]),
        if (prefill.isEmpty) SeqNode(),
      ]),
      enterSlot: 0,
    );
  }

  /// 切到当前函数调用的下一个参数；已经是最后一个就新建一个参数槽。
  ///
  /// 只能用在函数参数里（光标路径的最后一跳指向某个 FuncNode 的参数槽时）。
  void nextArgument() {
    if (cursor.steps.isEmpty) return;
    final here = cursor.steps.last;
    final parent = SlotPath(cursor.steps.sublist(0, cursor.steps.length - 1), 0);
    final siblings = slotAt(parent);
    if (here.child >= siblings.children.length) return;

    final node = siblings.children[here.child];
    if (node is! FuncNode) return;

    var target = here.slot + 1;
    if (target >= node.args.length) {
      node.args.add(SeqNode());
      target = node.args.length - 1;
    }
    cursor = parent.push(here.child, target);
  }

  // ------------------------------------------------------------------ 删除

  /// 槽里还有没填的空位（"还没填完的模板"）。
  static bool _incomplete(ExprNode n) => _slotsOf(n).any((s) => s.isEmpty);

  /// 退格。
  ///
  /// 三条规则，都是为了"手感"：
  ///  1. 数字字面量**逐位删** —— 计算器按退格是删一位，不是把整个数清掉。
  ///  2. 左边是**还没填完的模板**（还有空槽）就钻进去删，而不是整个删掉 ——
  ///     用户按了 `∫` 后悔，一按退格整块模板没了会很难受。
  ///  3. 左边是**已经填完的模板**就整个删掉 —— 否则光标会永远在模板内部打转，
  ///     根本删不掉它。
  void backspace() {
    final seq = current;

    if (cursor.offset > 0 && seq.children.isNotEmpty) {
      final node = seq.children[cursor.offset - 1];

      // 规则 1
      if (node is LitNode && _isNumberText(node.text) && node.text.length > 1) {
        seq.children[cursor.offset - 1] =
            LitNode(node.text.substring(0, node.text.length - 1));
        return;
      }

      final slots = _slotsOf(node);
      if (slots.isEmpty) {
        seq.children.removeAt(cursor.offset - 1);
        cursor = SlotPath(cursor.steps, cursor.offset - 1);
        return;
      }
      if (_incomplete(node)) {
        // 规则 2：钻进最后一个空槽
        final i = slots.lastIndexWhere((s) => s.isEmpty);
        cursor = cursor.push(cursor.offset - 1, i);
        return;
      }
      // 规则 3
      seq.children.removeAt(cursor.offset - 1);
      cursor = SlotPath(cursor.steps, cursor.offset - 1);
      return;
    }

    // 已经在槽的最左边：退回父槽
    final up = cursor.parent;
    if (up == null) return; // 根槽最左边，没得删

    final parentSeq = slotAt(SlotPath(up.steps, up.offset));
    final idx = up.offset - 1;
    if (idx >= 0 && idx < parentSeq.children.length) {
      final child = parentSeq.children[idx];
      // 从"还没填完的模板"里退出来时，顺手把它也删掉
      if (_incomplete(child)) {
        parentSeq.children.removeAt(idx);
        cursor = SlotPath(up.steps, idx);
        return;
      }
    }
    cursor = up;
  }

  /// 用另一个槽的内容整体替换（粘贴用）。光标落到末尾 —— 粘完接着打最自然。
  void replaceWith(SeqNode other) {
    root.children
      ..clear()
      ..addAll(other.children);
    cursor = SlotPath(const <SlotStep>[], root.children.length);
  }

  void clear() {
    root.children.clear();
    cursor = SlotPath.root;
  }

  // ------------------------------------------------------------------ 序列化成 Symja

  /// 整棵树 → 一条 Symja 表达式。
  String toSymja() => serializeSeq(root);


  /// 槽 → 表达式。空槽在 Symja 里写成 `Null`，求值时会明确报错而不是静默算错。
  String serializeSeq(SeqNode seq) {
    if (seq.isEmpty) return 'Null';
    return seq.children.map(serialize).join();
  }

  String serialize(ExprNode node) => switch (node) {
        LitNode l => l.text,
        FuncNode f => '${f.name}[${f.args.map(serializeSeq).join(', ')}]',
        FracNode f => '${_grouped(serializeSeq(f.num))}/${_grouped(serializeSeq(f.den))}',
        PowNode p => '${_grouped(serializeSeq(p.base))}^${_grouped(serializeSeq(p.exp))}',
        GroupNode g => '(${serializeSeq(g.inner)})',
        BraceNode b => '{${serializeSeq(b.inner)}}',
        BigOpNode b => _serializeBigOp(b),
        PostfixNode p => '${_grouped(serializeSeq(p.operand))}${p.op}',
      };

  /// 大运算符还原成 Symja 写法。
  static String _serializeBigOp(BigOpNode b) {
    final body = ExprDoc().serializeSeq(b.body);
    final v = ExprDoc().serializeSeq(b.variable);

    if (b.kind == 'Limit') {
      // Limit[f, x -> 0]
      final to = ExprDoc().serializeSeq(b.lower);
      return 'Limit[$body, $v -> $to]';
    }
    // 上下限都空 → 不定积分这种，只给变量
    if (b.lower.isEmpty && b.upper.isEmpty) {
      return '${b.kind}[$body, $v]';
    }
    final lo = ExprDoc().serializeSeq(b.lower);
    final hi = ExprDoc().serializeSeq(b.upper);
    return '${b.kind}[$body, {$v, $lo, $hi}]';
  }

  /// 复合结构当操作数时要加括号，否则 `x+1` 当分母会算错优先级。
  ///
  /// 但**不多加**：整体已经被一对括号包住的（`(x+1)`）不再套一层成 `((x+1))`；
  /// 单个项（字面量、函数调用）本来就不需要括号。
  String _grouped(String s) {
    if (s.isEmpty) return s;
    if (_isFullyParenthesized(s)) return s;
    if (_isSimpleTerm(s)) return s;
    return '($s)';
  }

  /// 整个串恰好被一对括号包住（括号配平、且中间没有提前闭合）。
  static bool _isFullyParenthesized(String s) {
    if (!s.startsWith('(') || !s.endsWith(')')) return false;
    var depth = 0;
    for (var i = 0; i < s.length; i++) {
      if (s[i] == '(') {
        depth++;
      } else if (s[i] == ')') {
        depth--;
        if (depth == 0) return i == s.length - 1;
      }
    }
    return false;
  }

  /// 顶层没有运算符 —— 单个字面量、函数调用或括号组，当操作数不需要括号。
  ///
  /// `[` `]` `{` `}` 也算一层，所以 `Sin[x+1]` 里的 `+` 不算顶层运算符 ——
  /// 它本来就不用括号。开头的正负号是正负号不是运算符，跳过。
  static bool _isSimpleTerm(String s) {
    var depth = 0;
    for (var i = 0; i < s.length; i++) {
      final c = s[i];
      if (c == '(' || c == '[' || c == '{') {
        depth++;
      } else if (c == ')' || c == ']' || c == '}') {
        depth--;
      } else if (depth == 0 && '+-*/^'.contains(c)) {
        if (i == 0 && (c == '-' || c == '+')) continue;
        return false;
      }
    }
    return true;
  }
}