!142 · krz/orgstar

Sources/OrgCore/Capture/Capture.swift +5 −2

		@@ -764,8 +764,10 @@ public enum Capture {
764	764	table = origin..<buffer.point
765	765	}
766	766	let rows = buffer.substring(table!.lowerBound, table!.upperBound).components(separatedBy: "\n")
	767	/// The start of the table's line `index`, within the table, as Org narrows to it.
767	768	func lineStart(_ index: Int) -> Int {
768		buffer.saveExcursion {
	769	guard index > 0 else { return table!.lowerBound }
	770	return buffer.saveExcursion {
769	771	buffer.point = table!.lowerBound
770	772	return buffer.forwardLine(index) == 0 ? min(buffer.point, table!.upperBound) : table!.upperBound
771	773	}
		@@ -777,7 +779,8 @@ public enum Capture {
777	779	guard let delta = Int(m.2.replacingOccurrences(of: "+", with: "")), (-999_999...999_999).contains(delta) else {
778	780	throw Failure.message("Invalid table line specification \"\(pos)\"")
779	781	}
780		buffer.point = lineStart(hlines[m.1.count - 1] + delta + (delta < 0 ? 0 : -1) + 1)
	782	// `forward-line` stops at the table's start, then one more line down.
	783	buffer.point = lineStart(max(0, hlines[m.1.count - 1] + delta + (delta < 0 ? 0 : -1)) + 1)
781	784	} else if options.prepend {
782	785	if let rule = rows.firstIndex(where: { $0.range(of: "^[ \\t]*\\\|-", options: .regularExpression) != nil }) {
783	786	let data = rows.indices.first { $0 > rule && rows[$0].range(of: "^[ \\t]*\\\|[^-]", options: .regularExpression) != nil }

Sources/OrgCore/Export/Citations.swift +9 −1

		@@ -399,7 +399,15 @@ struct CiteProcessor {
399	399	}
400	400	}
401	401	let tree = OrgParser.parse(text)
402		let citations = tree.root.descendants().filter { $0.kind == .citation }.compactMap { Self.parse($0.text) }
	402	// Keywords (`#+TITLE`) aren't part of the document Org processes citations in.
	403	var nodes: [SyntaxNode] = []
	404	func collect(_ node: SyntaxNode) {
	405	for child in node.children where child.kind != .keyword {
	406	if child.kind == .citation { nodes.append(child) } else { collect(child) }
	407	}
	408	}
	409	collect(tree.root)
	410	let citations = nodes.compactMap { Self.parse($0.text) }
403	411	var keys: [String] = []
404	412	for citation in citations { for r in citation.references where !keys.contains(r.key) { keys.append(r.key) } }
405	413	for citation in citations {

Sources/OrgCore/Export/HTMLExport.swift +7 −1

		@@ -47,8 +47,11 @@ public enum HTMLExport {
47	47	let meta = metadata(text, settings: settings)
48	48	let title = meta.title ?? fallbackTitle
49	49	let renderer = HTMLRenderer(settings: settings, options: options)
50		renderer.citations = CiteProcessor(text: text, directory: directory)
	50	// The title isn't part of the document Org processes citations in: they drop out.
	51	renderer.inTitle = true
51	52	let titleHTML = renderer.inlineString(title)
	53	renderer.inTitle = false
	54	renderer.citations = CiteProcessor(text: text, directory: directory)
52	55	var header = options.title ? "<h1 class=\"title\">\(titleHTML)</h1>\n" : ""
53	56	let byline = [options.author ? meta.author : nil, options.date ? meta.date : nil].compactMap { $0 }.filter { !$0.isEmpty }
54	57	if !byline.isEmpty { header += "<p class=\"byline\">\(byline.map(HTMLRenderer.escape).joined(separator: " · "))</p>\n" }
		@@ -107,6 +110,8 @@ final class HTMLRenderer {
107	110	private var ids: Set<String> = []
108	111	/// Citations and the bibliography, as `oc-basic` exports them.
109	112	var citations: CiteProcessor?
	113	/// Rendering the title, where Org exports citations as nothing.
	114	var inTitle = false
110	115
111	116	enum FootnoteContent {
112	117	case definition(String)
		@@ -702,6 +707,7 @@ final class HTMLRenderer {
702	707	guard node.tokens.first?.text == "@@html:" else { return "" }
703	708	return node.tokens.filter { $0.kind != .marker }.map(\.text).joined()
704	709	case .citation:
	710	if inTitle { return "" }
705	711	guard let pieces = citations?.next(node.text) else { return Self.escape(node.text) }
706	712	return render(pieces)
707	713	case .inlineBabelCall: return Self.escape(node.text)

Sources/OrgCore/Export/MarkdownExport.swift +6 −1

		@@ -6,9 +6,11 @@ public enum MarkdownExport {
6	6	/// `path` is the file's, for `#+bibliography:`.
7	7	public static func document(_ text: String, settings: OrgSettings = .default, path: String? = nil) -> String {
8	8	let renderer = MarkdownRenderer(settings: settings)
9		renderer.citations = CiteProcessor(text: text, directory: path.map { URL(fileURLWithPath: $0).deletingLastPathComponent() })
10	9	var out = ""
	10	renderer.inTitle = true
11	11	if let title = HTMLExport.metadata(text, settings: settings).title { out = "# " + renderer.inlineString(title) + "\n\n" }
	12	renderer.inTitle = false
	13	renderer.citations = CiteProcessor(text: text, directory: path.map { URL(fileURLWithPath: $0).deletingLastPathComponent() })
12	14	out += renderer.document(renderer.citations == nil ? text : CiteProcessor.removingNocite(text))
13	15	return out.trimmingCharacters(in: .newlines) + "\n"
14	16	}
		@@ -22,6 +24,8 @@ final class MarkdownRenderer {
22	24	private var anonymous = 0
23	25	/// Citations and the bibliography, as `oc-basic` exports them.
24	26	var citations: CiteProcessor?
	27	/// Rendering the title, where Org exports citations as nothing.
	28	var inTitle = false
25	29
26	30	init(settings: OrgSettings) {
27	31	self.settings = settings
		@@ -276,6 +280,7 @@ final class MarkdownRenderer {
276	280	guard node.tokens.first?.text == "@@html:" else { return "" }
277	281	return node.tokens.filter { $0.kind != .marker }.map(\.text).joined()
278	282	case .citation:
	283	if inTitle { return "" }
279	284	guard let pieces = citations?.next(node.text) else { return node.text }
280	285	return render(pieces)
281	286	case .inlineBabelCall: return node.text

Sources/OrgCore/LineDiff.swift added +138

		@@ -0,0 +1,138 @@
	1	import Foundation
	2
	3	// Line diffs: Myers over line ids, for merges, diffs and commands' edits.
	4
	5	/// Edits, in `old` coordinates and ascending order, that turn `old` into `new` line by line.
	6	public func lineEdits(from old: String, to new: String) -> [TextEdit] {
	7	let oldLines = textLines(old)
	8	let newLines = textLines(new)
	9	var ids = LineIDs()
	10	let pairs = matchingLines(ids.encode(oldLines), ids.encode(newLines))
	11	var offsets = [0]
	12	for line in oldLines { offsets.append(offsets.last! + line.utf16.count) }
	13	var edits: [TextEdit] = []
	14	var i = 0, j = 0
	15	for (pi, pj) in pairs + [(oldLines.count, newLines.count)] {
	16	if i < pi \|\| j < pj {
	17	edits.append(TextEdit(range: offsets[i]..<offsets[pi], replacement: newLines[j..<pj].joined()))
	18	}
	19	i = pi + 1
	20	j = pj + 1
	21	}
	22	return edits
	23	}
	24
	25	/// Lines with their endings.
	26	public func textLines(_ text: String) -> [String] {
	27	var lines: [String] = []
	28	var current = ""
	29	for scalar in text.unicodeScalars {
	30	current.unicodeScalars.append(scalar)
	31	if scalar == "\n" {
	32	lines.append(current)
	33	current = ""
	34	}
	35	}
	36	if !current.isEmpty { lines.append(current) }
	37	return lines
	38	}
	39
	40	public struct LineIDs {
	41	private var ids: [String: Int] = [:]
	42
	43	public init() {}
	44
	45	public mutating func encode(_ lines: [String]) -> [Int] {
	46	lines.map { line in
	47	if let id = ids[line] { return id }
	48	let id = ids.count
	49	ids[line] = id
	50	return id
	51	}
	52	}
	53	}
	54
	55	/// Matched index pairs of a longest common subsequence, ascending. Common prefix and suffix
	56	/// are matched directly; Myers' algorithm handles the middle. When the middle differs by more
	57	/// than the memory budget allows, it is treated as having no matches.
	58	public func matchingLines(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
	59	var prefix = 0
	60	while prefix < a.count, prefix < b.count, a[prefix] == b[prefix] { prefix += 1 }
	61	var suffix = 0
	62	while suffix < a.count - prefix, suffix < b.count - prefix, a[a.count - 1 - suffix] == b[b.count - 1 - suffix] {
	63	suffix += 1
	64	}
	65	var pairs = (0..<prefix).map { ($0, $0) }
	66	let middleA = Array(a[prefix..<(a.count - suffix)])
	67	let middleB = Array(b[prefix..<(b.count - suffix)])
	68	pairs += myers(middleA, middleB).map { ($0.0 + prefix, $0.1 + prefix) }
	69	pairs += (0..<suffix).map { (a.count - suffix + $0, b.count - suffix + $0) }
	70	return pairs
	71	}
	72
	73	private func myers(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
	74	let n = a.count, m = b.count
	75	guard n > 0, m > 0 else { return [] }
	76	let maxD = n + m
	77	let offset = maxD + 1
	78	// Each step keeps a copy of the frontier for backtracking; cap that at ~20M entries.
	79	let budget = max(1, 20_000_000 / (2 * maxD + 3))
	80	var v = [Int](repeating: 0, count: 2 * maxD + 3)
	81	var trace: [[Int]] = []
	82	var found = false
	83	search: for d in 0...min(maxD, budget) {
	84	trace.append(v)
	85	for k in stride(from: -d, through: d, by: 2) {
	86	var x = (k == -d \|\| (k != d && v[offset + k - 1] < v[offset + k + 1])) ? v[offset + k + 1] : v[offset + k - 1] + 1
	87	var y = x - k
	88	while x < n, y < m, a[x] == b[y] {
	89	x += 1
	90	y += 1
	91	}
	92	v[offset + k] = x
	93	if x >= n, y >= m {
	94	found = true
	95	break search
	96	}
	97	}
	98	}
	99	guard found else { return [] }
	100
	101	var pairs: [(Int, Int)] = []
	102	var x = n, y = m
	103	for d in stride(from: trace.count - 1, through: 0, by: -1) {
	104	let v = trace[d]
	105	let k = x - y
	106	let previousK = (k == -d \|\| (k != d && v[offset + k - 1] < v[offset + k + 1])) ? k + 1 : k - 1
	107	let previousX = v[offset + previousK]
	108	let previousY = previousX - previousK
	109	while x > previousX, y > previousY {
	110	pairs.append((x - 1, y - 1))
	111	x -= 1
	112	y -= 1
	113	}
	114	if d > 0 {
	115	x = previousX
	116	y = previousY
	117	}
	118	}
	119	return pairs.reversed()
	120	}
	121
	122
	123	/// An edit spanning several lines as the lines it changes, so what lies between (a folded
	124	/// heading) is left alone: a command changing the text in two places gives two edits. For
	125	/// editors applying edits; commands still return one.
	126	public func splitByLines(_ edit: TextEdit, in text: String) -> [TextEdit] {
	127	let ns = text as NSString
	128	let start = ns.lineRange(for: NSRange(location: edit.range.lowerBound, length: 0)).location
	129	var end = edit.range.upperBound
	130	if end < ns.length, end == 0 \|\| ns.character(at: end - 1) != 10 {
	131	end = NSMaxRange(ns.lineRange(for: NSRange(location: end, length: 0)))
	132	}
	133	let old = ns.substring(with: NSRange(start..<end))
	134	guard old.utf16.lazy.filter({ $0 == 10 }).count >= 2 else { return [edit] }
	135	let new = ns.substring(with: NSRange(start..<edit.range.lowerBound)) + edit.replacement + ns.substring(with: NSRange(edit.range.upperBound..<end))
	136	let edits = lineEdits(from: old, to: new).map { TextEdit(range: ($0.range.lowerBound + start)..<($0.range.upperBound + start), replacement: $0.replacement) }
	137	return edits.isEmpty ? [edit] : edits
	138	}

Sources/OrgDocument/Merge.swift −115

		@@ -59,121 +59,6 @@ public func threeWayMerge(base: String, ours: String, theirs: String) -> MergeRe
59	59	return conflicts.isEmpty ? .merged(merged.joined()) : .conflict(conflicts)
60	60	}
61	61
62		/// Edits, in `old` coordinates and ascending order, that turn `old` into `new` line by line.
63		public func lineEdits(from old: String, to new: String) -> [TextEdit] {
64		let oldLines = textLines(old)
65		let newLines = textLines(new)
66		var ids = LineIDs()
67		let pairs = matchingLines(ids.encode(oldLines), ids.encode(newLines))
68		var offsets = [0]
69		for line in oldLines { offsets.append(offsets.last! + line.utf16.count) }
70		var edits: [TextEdit] = []
71		var i = 0, j = 0
72		for (pi, pj) in pairs + [(oldLines.count, newLines.count)] {
73		if i < pi \|\| j < pj {
74		edits.append(TextEdit(range: offsets[i]..<offsets[pi], replacement: newLines[j..<pj].joined()))
75		}
76		i = pi + 1
77		j = pj + 1
78		}
79		return edits
80		}
81
82		/// Lines with their endings.
83		func textLines(_ text: String) -> [String] {
84		var lines: [String] = []
85		var current = ""
86		for scalar in text.unicodeScalars {
87		current.unicodeScalars.append(scalar)
88		if scalar == "\n" {
89		lines.append(current)
90		current = ""
91		}
92		}
93		if !current.isEmpty { lines.append(current) }
94		return lines
95		}
96
97		struct LineIDs {
98		private var ids: [String: Int] = [:]
99
100		mutating func encode(_ lines: [String]) -> [Int] {
101		lines.map { line in
102		if let id = ids[line] { return id }
103		let id = ids.count
104		ids[line] = id
105		return id
106		}
107		}
108		}
109
110		/// Matched index pairs of a longest common subsequence, ascending. Common prefix and suffix
111		/// are matched directly; Myers' algorithm handles the middle. When the middle differs by more
112		/// than the memory budget allows, it is treated as having no matches.
113		func matchingLines(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
114		var prefix = 0
115		while prefix < a.count, prefix < b.count, a[prefix] == b[prefix] { prefix += 1 }
116		var suffix = 0
117		while suffix < a.count - prefix, suffix < b.count - prefix, a[a.count - 1 - suffix] == b[b.count - 1 - suffix] {
118		suffix += 1
119		}
120		var pairs = (0..<prefix).map { ($0, $0) }
121		let middleA = Array(a[prefix..<(a.count - suffix)])
122		let middleB = Array(b[prefix..<(b.count - suffix)])
123		pairs += myers(middleA, middleB).map { ($0.0 + prefix, $0.1 + prefix) }
124		pairs += (0..<suffix).map { (a.count - suffix + $0, b.count - suffix + $0) }
125		return pairs
126		}
127
128		private func myers(_ a: [Int], _ b: [Int]) -> [(Int, Int)] {
129		let n = a.count, m = b.count
130		guard n > 0, m > 0 else { return [] }
131		let maxD = n + m
132		let offset = maxD + 1
133		// Each step keeps a copy of the frontier for backtracking; cap that at ~20M entries.
134		let budget = max(1, 20_000_000 / (2 * maxD + 3))
135		var v = [Int](repeating: 0, count: 2 * maxD + 3)
136		var trace: [[Int]] = []
137		var found = false
138		search: for d in 0...min(maxD, budget) {
139		trace.append(v)
140		for k in stride(from: -d, through: d, by: 2) {
141		var x = (k == -d \|\| (k != d && v[offset + k - 1] < v[offset + k + 1])) ? v[offset + k + 1] : v[offset + k - 1] + 1
142		var y = x - k
143		while x < n, y < m, a[x] == b[y] {
144		x += 1
145		y += 1
146		}
147		v[offset + k] = x
148		if x >= n, y >= m {
149		found = true
150		break search
151		}
152		}
153		}
154		guard found else { return [] }
155
156		var pairs: [(Int, Int)] = []
157		var x = n, y = m
158		for d in stride(from: trace.count - 1, through: 0, by: -1) {
159		let v = trace[d]
160		let k = x - y
161		let previousK = (k == -d \|\| (k != d && v[offset + k - 1] < v[offset + k + 1])) ? k + 1 : k - 1
162		let previousX = v[offset + previousK]
163		let previousY = previousX - previousK
164		while x > previousX, y > previousY {
165		pairs.append((x - 1, y - 1))
166		x -= 1
167		y -= 1
168		}
169		if d > 0 {
170		x = previousX
171		y = previousY
172		}
173		}
174		return pairs.reversed()
175		}
176
177	62	/// One line of a diff, with its ending.
178	63	public struct DiffLine: Sendable, Equatable {
179	64	public enum Kind: Sendable, Equatable { case same, removed, added }

Sources/OrgEditorAppKit/OrgEditor.swift +3 −1

		@@ -964,7 +964,9 @@ public final class OrgEditor: NSObject {
964	964	guard !edits.isEmpty, let storage = textView.textStorage else { return }
965	965	textView.breakUndoCoalescing()
966	966	textView.undoManager?.beginUndoGrouping()
967		for edit in edits.sorted(by: { $0.range.lowerBound > $1.range.lowerBound }) {
	967	// By lines, so a fold between two changes stays.
	968	let text = storage.string
	969	for edit in edits.flatMap({ splitByLines($0, in: text) }).sorted(by: { $0.range.lowerBound > $1.range.lowerBound }) {
968	970	let range = NSRange(edit.range)
969	971	guard textView.shouldChangeText(in: range, replacementString: edit.replacement) else { continue }
970	972	storage.replaceCharacters(in: range, with: edit.replacement)

Sources/OrgstarMobile/MobileEditor.swift +3 −3

		@@ -319,7 +319,8 @@ final class MobileEditor: NSObject, DocumentBuffer {
319	319	// keyboard's substitutions (smart dashes) when another view has the keyboard.
320	320	let storage = textView.textStorage
321	321	let old = storage.string as NSString
322		let ascending = edits.sorted { $0.range.lowerBound < $1.range.lowerBound }
	322	// By lines, so a fold between two changes stays.
	323	let ascending = edits.flatMap { splitByLines($0, in: storage.string) }.sorted { $0.range.lowerBound < $1.range.lowerBound }
323	324	var inverse: [TextEdit] = []
324	325	var delta = 0
325	326	for edit in ascending {
		@@ -329,11 +330,10 @@ final class MobileEditor: NSObject, DocumentBuffer {
329	330	delta += length - edit.range.count
330	331	}
331	332	let caret = textView.selectedRange
332		storage.beginEditing()
	333	// One at a time, last first: each is processed alone, so folds between them stay.
333	334	for edit in ascending.reversed() {
334	335	storage.replaceCharacters(in: NSRange(edit.range), with: edit.replacement)
335	336	}
336		storage.endEditing()
337	337	textView.undoManager?.registerUndo(withTarget: self) { editor in
338	338	editor.applyEdits(inverse)
339	339	editor.textView.selectedRange = caret

Tests/OrgCoreTests/CaptureTests.swift +2

		@@ -153,6 +153,8 @@ struct CaptureTests {
153	153	CaptureTemplate(key: "x", name: "", kind: .tableLine, target: .headline(file: "", headline: "Inbox"), template: "\| first %? \|\n\| second \|",
154	154	options: .init(tableLinePos: "I+1")),
155	155	CaptureTemplate(key: "x", name: "", kind: .tableLine, target: .file(""), template: "\| %? \|"),
	156	CaptureTemplate(key: "x", name: "", kind: .tableLine, target: .headline(file: "", headline: "Inbox"), template: "\| far %? \|",
	157	options: .init(tableLinePos: "I-9")),
156	158	]
157	159
158	160	@Test(.enabled(if: ProcessInfo.processInfo.environment["ORGSTAR_SKIP_ORACLE"] == nil))

Tests/OrgCoreTests/CitationTests.swift +11

		@@ -98,6 +98,17 @@ struct CitationTests {
98	98	#expect(!page.contains("[cite"))
99	99	}
100	100
	101	@Test func aTitleCitationLeavesTheBodysAlone() throws {
	102	let folder = FileManager.default.temporaryDirectory.appendingPathComponent("orgstar-cite-\(UUID().uuidString)")
	103	try FileManager.default.createDirectory(at: folder, withIntermediateDirectories: true)
	104	defer { try? FileManager.default.removeItem(at: folder) }
	105	try Self.bib.write(to: folder.appendingPathComponent("refs.bib"), atomically: true, encoding: .utf8)
	106	let page = HTMLExport.page("#+bibliography: refs.bib\n#+TITLE: On [cite:@doe2020]\nSee [cite:@doe2020].\n", fallbackTitle: "t",
	107	path: folder.appendingPathComponent("doc.org").path)
	108	#expect(page.contains("<h1 class=\"title\">On</h1>"))
	109	#expect(page.contains("<p>See (Doe, Jane and Roe, Richard, 2020).</p>"))
	110	}
	111
101	112	@Test(.enabled(if: oracle))
102	113	func authorYearMatchesOcBasic() throws {
103	114	try compare("#+bibliography: refs.bib\n#+bibliography: more.json\n" + Self.body)

Tests/OrgCoreTests/LineDiffTests.swift added +24

		@@ -0,0 +1,24 @@
	1	import Foundation
	2	import Testing
	3	@testable import OrgCore
	4
	5	struct LineDiffTests {
	6	@Test func splitsAnEditSpanningSeveralLinesIntoTheLinesItChanges() {
	7	let text = "* Top\nText here.\n* Folded\n** Child\nbody\n* End\n"
	8	let new = "* Top\nText here.[fn:1]\n* Folded\n** Child\nbody\n* End\n\n* Footnotes\n\n[fn:1] \n"
	9	let one = TextEdit.between(text, new)
	10	#expect(one.count == 1)
	11	let split = splitByLines(one[0], in: text)
	12	#expect(split.count == 2)
	13	#expect(split.allSatisfy { !(text as NSString).substring(with: NSRange($0.range)).contains("* Folded") })
	14	var result = text
	15	for edit in split.sorted(by: { $0.range.lowerBound > $1.range.lowerBound }) { result = edit.apply(to: result) }
	16	#expect(result == new)
	17	}
	18
	19	@Test func leavesAnEditWithinALineAlone() {
	20	let text = "* a\nbc\n"
	21	let edit = TextEdit(range: 4..<5, replacement: "x")
	22	#expect(splitByLines(edit, in: text) == [edit])
	23	}
	24	}

Keep folds through multi-place edits; title citations; table-line clamp !142