1 /* Title: Pure/PIDE/document.scala
4 Document as collection of named nodes, each consisting of an editable
5 list of commands, associated with asynchronous execution process.
11 import scala.collection.mutable
16 /* formal identifiers */
19 val ID = Properties.Value.Long
26 val new_id = Counter()
30 /** document structure **/
32 /* individual nodes */
34 type Edit[A, B] = (Node.Name, Node.Edit[A, B])
35 type Edit_Text = Edit[Text.Edit, Text.Perspective]
36 type Edit_Command = Edit[(Option[Command], Option[Command]), Command.Perspective]
38 type Node_Header = Exn.Result[Node.Deps]
42 sealed case class Deps(
44 keywords: List[Outer_Syntax.Decl],
45 uses: List[(String, Boolean)])
49 val empty = Name("", "", "")
50 def apply(path: Path): Name =
52 val node = path.implode
53 val dir = path.dir.implode
54 val theory = Thy_Header.thy_name(node) getOrElse error("Bad theory file name: " + path)
55 Name(node, dir, theory)
58 object Ordering extends scala.math.Ordering[Name]
60 def compare(name1: Name, name2: Name): Int = name1.node compare name2.node
63 sealed case class Name(node: String, dir: String, theory: String)
65 override def hashCode: Int = node.hashCode
66 override def equals(that: Any): Boolean =
68 case other: Name => node == other.node
71 override def toString: String = theory
74 sealed abstract class Edit[A, B]
76 def foreach(f: A => Unit)
79 case Edits(es) => es.foreach(f)
84 case class Clear[A, B]() extends Edit[A, B]
85 case class Edits[A, B](edits: List[A]) extends Edit[A, B]
86 case class Header[A, B](header: Node_Header) extends Edit[A, B]
87 case class Perspective[A, B](perspective: B) extends Edit[A, B]
89 def command_starts(commands: Iterator[Command], offset: Text.Offset = 0)
90 : Iterator[(Command, Text.Offset)] =
93 for (command <- commands) yield {
100 private val block_size = 1024
102 val empty: Node = new Node()
105 final class Node private(
106 val header: Node_Header = Exn.Exn(ERROR("Bad theory header")),
107 val perspective: Command.Perspective = Command.Perspective.empty,
108 val blobs: Map[String, Blob] = Map.empty,
109 val commands: Linear_Set[Command] = Linear_Set.empty)
111 def clear: Node = new Node(header = header)
113 def update_header(new_header: Node_Header): Node =
114 new Node(new_header, perspective, blobs, commands)
116 def update_perspective(new_perspective: Command.Perspective): Node =
117 new Node(header, new_perspective, blobs, commands)
119 def update_blobs(new_blobs: Map[String, Blob]): Node =
120 new Node(header, perspective, new_blobs, commands)
122 def update_commands(new_commands: Linear_Set[Command]): Node =
123 new Node(header, perspective, blobs, new_commands)
125 def imports: List[Node.Name] =
126 header match { case Exn.Res(deps) => deps.imports case _ => Nil }
128 def keywords: List[Outer_Syntax.Decl] =
129 header match { case Exn.Res(deps) => deps.keywords case _ => Nil }
134 private lazy val full_index: (Array[(Command, Text.Offset)], Text.Range) =
136 val blocks = new mutable.ListBuffer[(Command, Text.Offset)]
139 for ((command, start) <- Node.command_starts(commands.iterator)) {
140 last_stop = start + command.length
141 while (last_stop + 1 > next_block) {
142 blocks += (command -> start)
143 next_block += Node.block_size
146 (blocks.toArray, Text.Range(0, last_stop))
149 def full_range: Text.Range = full_index._2
151 def command_range(i: Text.Offset = 0): Iterator[(Command, Text.Offset)] =
153 if (!commands.isEmpty && full_range.contains(i)) {
154 val (cmd0, start0) = full_index._1(i / Node.block_size)
155 Node.command_starts(commands.iterator(cmd0), start0) dropWhile {
156 case (cmd, start) => start + cmd.length <= i }
161 def command_range(range: Text.Range): Iterator[(Command, Text.Offset)] =
162 command_range(range.start) takeWhile { case (_, start) => start < range.stop }
164 def command_at(i: Text.Offset): Option[(Command, Text.Offset)] =
166 val range = command_range(i)
167 if (range.hasNext) Some(range.next) else None
170 def command_start(cmd: Command): Option[Text.Offset] =
171 Node.command_starts(commands.iterator).find(_._1 == cmd).map(_._2)
175 /* development graph */
179 val empty: Nodes = new Nodes(Graph.empty(Node.Name.Ordering))
182 final class Nodes private(graph: Graph[Node.Name, Node])
184 def get_name(s: String): Option[Node.Name] =
185 graph.keys.find(name => name.node == s)
187 def apply(name: Node.Name): Node =
188 graph.default_node(name, Node.empty).get_node(name)
190 def + (entry: (Node.Name, Node)): Nodes =
192 val (name, node) = entry
193 val imports = node.imports
195 (graph.default_node(name, Node.empty) /: imports)((g, p) => g.default_node(p, Node.empty))
196 val graph2 = (graph1 /: graph1.imm_preds(name))((g, dep) => g.del_edge(dep, name))
197 val graph3 = (graph2 /: imports)((g, dep) => g.add_edge(dep, name))
198 new Nodes(graph3.map_node(name, _ => node))
201 def entries: Iterator[(Node.Name, Node)] =
202 graph.entries.map({ case (name, (node, _)) => (name, node) })
204 def descendants(names: List[Node.Name]): List[Node.Name] = graph.all_succs(names)
205 def topological_order: List[Node.Name] = graph.topological_order
212 /* particular document versions */
216 val init: Version = new Version()
218 def make(syntax: Outer_Syntax, nodes: Nodes): Version =
219 new Version(new_id(), syntax, nodes)
222 final class Version private(
223 val id: Version_ID = no_id,
224 val syntax: Outer_Syntax = Outer_Syntax.empty,
225 val nodes: Nodes = Nodes.empty)
227 def is_init: Boolean = id == no_id
231 /* changes of plain text, eventually resulting in document edits */
235 val init: Change = new Change()
237 def make(previous: Future[Version], edits: List[Edit_Text], version: Future[Version]): Change =
238 new Change(Some(previous), edits, version)
241 final class Change private(
242 val previous: Option[Future[Version]] = Some(Future.value(Version.init)),
243 val edits: List[Edit_Text] = Nil,
244 val version: Future[Version] = Future.value(Version.init))
246 def is_finished: Boolean =
247 (previous match { case None => true case Some(future) => future.is_finished }) &&
250 def truncate: Change = new Change(None, Nil, version)
254 /* history navigation */
258 val init: History = new History()
261 final class History private(
262 val undo_list: List[Change] = List(Change.init)) // non-empty list
264 def tip: Change = undo_list.head
265 def + (change: Change): History = new History(change :: undo_list)
267 def prune(check: Change => Boolean, retain: Int): Option[(List[Change], History)] =
269 val n = undo_list.iterator.zipWithIndex.find(p => check(p._1)).get._2 + 1
270 val (retained, dropped) = undo_list.splitAt(n max retain)
272 retained.splitAt(retained.length - 1) match {
273 case (prefix, List(last)) => Some(dropped, new History(prefix ::: List(last.truncate)))
281 /** global state -- document structure, execution process, editing history **/
283 abstract class Snapshot
288 val is_outdated: Boolean
289 def convert(i: Text.Offset): Text.Offset
290 def convert(range: Text.Range): Text.Range
291 def revert(i: Text.Offset): Text.Offset
292 def revert(range: Text.Range): Text.Range
293 def cumulate_markup[A](range: Text.Range, info: A, elements: Option[Set[String]],
294 result: PartialFunction[(A, Text.Markup), A]): Stream[Text.Info[A]]
295 def select_markup[A](range: Text.Range, elements: Option[Set[String]],
296 result: PartialFunction[Text.Markup, A]): Stream[Text.Info[A]]
300 (List[(Document.Command_ID, Option[Document.Exec_ID])], // exec state assignment
301 List[(String, Option[Document.Command_ID])]) // last exec
305 class Fail(state: State) extends Exception
309 val init: Assignment = new Assignment()
312 final class Assignment private(
313 val command_execs: Map[Command_ID, Exec_ID] = Map.empty,
314 val last_execs: Map[String, Option[Command_ID]] = Map.empty,
315 val is_finished: Boolean = false)
317 def check_finished: Assignment = { require(is_finished); this }
318 def unfinished: Assignment = new Assignment(command_execs, last_execs, false)
320 def assign(add_command_execs: List[(Command_ID, Option[Exec_ID])],
321 add_last_execs: List[(String, Option[Command_ID])]): Assignment =
323 require(!is_finished)
325 (command_execs /: add_command_execs) {
326 case (res, (command_id, None)) => res - command_id
327 case (res, (command_id, Some(exec_id))) => res + (command_id -> exec_id)
329 new Assignment(command_execs1, last_execs ++ add_last_execs, true)
334 State().define_version(Version.init, Assignment.init).assign(Version.init.id)._2
337 final case class State private(
338 val versions: Map[Version_ID, Version] = Map.empty,
339 val commands: Map[Command_ID, Command.State] = Map.empty, // static markup from define_command
340 val execs: Map[Exec_ID, Command.State] = Map.empty, // dynamic markup from execution
341 val assignments: Map[Version_ID, State.Assignment] = Map.empty,
342 val history: History = History.init)
344 private def fail[A]: A = throw new State.Fail(this)
346 def define_version(version: Version, assignment: State.Assignment): State =
349 copy(versions = versions + (id -> version),
350 assignments = assignments + (id -> assignment.unfinished))
353 def define_command(command: Command): State =
356 copy(commands = commands + (id -> command.empty_state))
359 def defined_command(id: Command_ID): Boolean = commands.isDefinedAt(id)
361 def find_command(version: Version, id: ID): Option[(Node, Command)] =
362 commands.get(id) orElse execs.get(id) match {
365 val command = st.command
366 val node = version.nodes(command.node_name)
367 Some((node, command))
370 def the_version(id: Version_ID): Version = versions.getOrElse(id, fail)
371 def the_command(id: Command_ID): Command.State = commands.getOrElse(id, fail) // FIXME rename
372 def the_exec(id: Exec_ID): Command.State = execs.getOrElse(id, fail)
373 def the_assignment(version: Version): State.Assignment =
374 assignments.getOrElse(version.id, fail)
376 def accumulate(id: ID, message: XML.Elem): (Command.State, State) =
377 execs.get(id) match {
379 val new_st = st + message
380 (new_st, copy(execs = execs + (id -> new_st)))
382 commands.get(id) match {
384 val new_st = st + message
385 (new_st, copy(commands = commands + (id -> new_st)))
390 def assign(id: Version_ID, arg: Assign = (Nil, Nil)): (List[Command], State) =
392 val version = the_version(id)
393 val (command_execs, last_execs) = arg
395 val (changed_commands, new_execs) =
396 ((Nil: List[Command], execs) /: command_execs) {
397 case ((commands1, execs1), (cmd_id, exec)) =>
398 val st = the_command(cmd_id)
399 val commands2 = st.command :: commands1
403 case Some(exec_id) => execs1 + (exec_id -> st)
407 val new_assignment = the_assignment(version).assign(command_execs, last_execs)
408 val new_state = copy(assignments = assignments + (id -> new_assignment), execs = new_execs)
410 (changed_commands, new_state)
413 def is_assigned(version: Version): Boolean =
414 assignments.get(version.id) match {
415 case Some(assgn) => assgn.is_finished
419 def is_stable(change: Change): Boolean =
420 change.is_finished && is_assigned(change.version.get_finished)
422 def recent_finished: Change = history.undo_list.find(_.is_finished) getOrElse fail
423 def recent_stable: Change = history.undo_list.find(is_stable) getOrElse fail
424 def tip_stable: Boolean = is_stable(history.tip)
425 def tip_version: Version = history.tip.version.get_finished
427 def last_exec_offset(name: Node.Name): Text.Offset =
429 val version = tip_version
430 the_assignment(version).last_execs.get(name.node) match {
431 case Some(Some(id)) =>
432 val node = version.nodes(name)
433 val cmd = the_command(id).command
434 node.command_start(cmd) match {
436 case Some(start) => start + cmd.length
442 def continue_history(
443 previous: Future[Version],
444 edits: List[Edit_Text],
445 version: Future[Version]): (Change, State) =
447 val change = Change.make(previous, edits, version)
448 (change, copy(history = history + change))
451 def prune_history(retain: Int = 0): (List[Version], State) =
453 history.prune(is_stable, retain) match {
454 case Some((dropped, history1)) =>
455 val dropped_versions = dropped.map(change => change.version.get_finished)
456 val state1 = copy(history = history1)
457 (dropped_versions, state1)
462 def removed_versions(removed: List[Version_ID]): State =
464 val versions1 = versions -- removed
465 val assignments1 = assignments -- removed
466 var commands1 = Map.empty[Command_ID, Command.State]
467 var execs1 = Map.empty[Exec_ID, Command.State]
469 (version_id, version) <- versions1.iterator
470 command_execs = assignments1(version_id).command_execs
471 (_, node) <- version.nodes.entries
472 command <- node.commands.iterator
475 if (!commands1.isDefinedAt(id) && commands.isDefinedAt(id))
476 commands1 += (id -> commands(id))
477 if (command_execs.isDefinedAt(id)) {
478 val exec_id = command_execs(id)
479 if (!execs1.isDefinedAt(exec_id) && execs.isDefinedAt(exec_id))
480 execs1 += (exec_id -> execs(exec_id))
483 copy(versions = versions1, commands = commands1, execs = execs1, assignments = assignments1)
486 def command_state(version: Version, command: Command): Command.State =
488 require(is_assigned(version))
490 the_exec(the_assignment(version).check_finished.command_execs
491 .getOrElse(command.id, fail))
493 catch { case _: State.Fail => command.empty_state }
497 // persistent user-view
498 def snapshot(name: Node.Name, pending_edits: List[Text.Edit]): Snapshot =
500 val stable = recent_stable
501 val latest = history.tip
503 // FIXME proper treatment of removed nodes
505 (pending_edits /: history.undo_list.takeWhile(_ != stable))((edits, change) =>
506 (for ((a, Node.Edits(es)) <- change.edits if a == name) yield es).flatten ::: edits)
507 lazy val reverse_edits = edits.reverse
511 val state = State.this
512 val version = stable.version.get_finished
513 val node = version.nodes(name)
514 val is_outdated = !(pending_edits.isEmpty && latest == stable)
516 def convert(offset: Text.Offset) = (offset /: edits)((i, edit) => edit.convert(i))
517 def revert(offset: Text.Offset) = (offset /: reverse_edits)((i, edit) => edit.revert(i))
518 def convert(range: Text.Range) = (range /: edits)((r, edit) => edit.convert(r))
519 def revert(range: Text.Range) = (range /: reverse_edits)((r, edit) => edit.revert(r))
521 def cumulate_markup[A](range: Text.Range, info: A, elements: Option[Set[String]],
522 result: PartialFunction[(A, Text.Markup), A]): Stream[Text.Info[A]] =
524 val former_range = revert(range)
526 (command, command_start) <- node.command_range(former_range).toStream
527 Text.Info(r0, a) <- state.command_state(version, command).markup.
528 cumulate[A]((former_range - command_start).restrict(command.range), info, elements,
530 case (a, Text.Info(r0, b))
531 if result.isDefinedAt((a, Text.Info(convert(r0 + command_start), b))) =>
532 result((a, Text.Info(convert(r0 + command_start), b)))
534 } yield Text.Info(convert(r0 + command_start), a)
537 def select_markup[A](range: Text.Range, elements: Option[Set[String]],
538 result: PartialFunction[Text.Markup, A]): Stream[Text.Info[A]] =
541 new PartialFunction[(Option[A], Text.Markup), Option[A]] {
542 def isDefinedAt(arg: (Option[A], Text.Markup)): Boolean = result.isDefinedAt(arg._2)
543 def apply(arg: (Option[A], Text.Markup)): Option[A] = Some(result(arg._2))
545 for (Text.Info(r, Some(x)) <- cumulate_markup(range, None, elements, result1))
546 yield Text.Info(r, x)