src/Pure/PIDE/document.scala
author wenzelm
Mon Jul 04 22:25:33 2011 +0200 (2011-07-04)
changeset 43662 e3175ec00311
parent 43427 5c716a68931a
child 43697 77ce24aa1770
permissions -rw-r--r--
Document.no_id/new_id as in ML (new_id *could* be session-specific but it isn't right now);
     1 /*  Title:      Pure/PIDE/document.scala
     2     Author:     Makarius
     3 
     4 Document as collection of named nodes, each consisting of an editable
     5 list of commands, associated with asynchronous execution process.
     6 */
     7 
     8 package isabelle
     9 
    10 
    11 import scala.collection.mutable
    12 
    13 
    14 object Document
    15 {
    16   /* formal identifiers */
    17 
    18   type ID = Long
    19 
    20   object ID
    21   {
    22     def apply(id: ID): String = Markup.Long.apply(id)
    23     def unapply(s: String): Option[ID] = Markup.Long.unapply(s)
    24   }
    25 
    26   type Version_ID = ID
    27   type Command_ID = ID
    28   type Exec_ID = ID
    29 
    30   val no_id: ID = 0
    31   val new_id = new Counter
    32 
    33 
    34 
    35   /** document structure **/
    36 
    37   /* named nodes -- development graph */
    38 
    39   type Edit[A] =
    40    (String,  // node name
    41     Option[List[A]])  // None: remove node, Some: edit content
    42 
    43   type Edit_Text = Edit[Text.Edit]
    44   type Edit_Command = Edit[(Option[Command], Option[Command])]
    45   type Edit_Command_ID = Edit[(Option[Command_ID], Option[Command_ID])]
    46 
    47   object Node
    48   {
    49     val empty: Node = new Node(Linear_Set())
    50 
    51     def command_starts(commands: Iterator[Command], offset: Text.Offset = 0)
    52       : Iterator[(Command, Text.Offset)] =
    53     {
    54       var i = offset
    55       for (command <- commands) yield {
    56         val start = i
    57         i += command.length
    58         (command, start)
    59       }
    60     }
    61   }
    62 
    63   private val block_size = 1024
    64 
    65   class Node(val commands: Linear_Set[Command])
    66   {
    67     private lazy val full_index: (Array[(Command, Text.Offset)], Text.Range) =
    68     {
    69       val blocks = new mutable.ListBuffer[(Command, Text.Offset)]
    70       var next_block = 0
    71       var last_stop = 0
    72       for ((command, start) <- Node.command_starts(commands.iterator)) {
    73         last_stop = start + command.length
    74         while (last_stop + 1 > next_block) {
    75           blocks += (command -> start)
    76           next_block += block_size
    77         }
    78       }
    79       (blocks.toArray, Text.Range(0, last_stop))
    80     }
    81 
    82     def full_range: Text.Range = full_index._2
    83 
    84     def command_range(i: Text.Offset = 0): Iterator[(Command, Text.Offset)] =
    85     {
    86       if (!commands.isEmpty && full_range.contains(i)) {
    87         val (cmd0, start0) = full_index._1(i / block_size)
    88         Node.command_starts(commands.iterator(cmd0), start0) dropWhile {
    89           case (cmd, start) => start + cmd.length <= i }
    90       }
    91       else Iterator.empty
    92     }
    93 
    94     def command_range(range: Text.Range): Iterator[(Command, Text.Offset)] =
    95       command_range(range.start) takeWhile { case (_, start) => start < range.stop }
    96 
    97     def command_at(i: Text.Offset): Option[(Command, Text.Offset)] =
    98     {
    99       val range = command_range(i)
   100       if (range.hasNext) Some(range.next) else None
   101     }
   102 
   103     def proper_command_at(i: Text.Offset): Option[Command] =
   104       command_at(i) match {
   105         case Some((command, _)) =>
   106           commands.reverse_iterator(command).find(cmd => !cmd.is_ignored)
   107         case None => None
   108       }
   109 
   110     def command_start(cmd: Command): Option[Text.Offset] =
   111       command_starts.find(_._1 == cmd).map(_._2)
   112 
   113     def command_starts: Iterator[(Command, Text.Offset)] =
   114       Node.command_starts(commands.iterator)
   115   }
   116 
   117 
   118 
   119   /** versioning **/
   120 
   121   /* particular document versions */
   122 
   123   object Version
   124   {
   125     val init: Version = new Version(no_id, Map().withDefaultValue(Node.empty))
   126   }
   127 
   128   class Version(val id: Version_ID, val nodes: Map[String, Node])
   129 
   130 
   131   /* changes of plain text, eventually resulting in document edits */
   132 
   133   object Change
   134   {
   135     val init = new Change(Future.value(Version.init), Nil, Future.value(Nil, Version.init))
   136   }
   137 
   138   class Change(
   139     val previous: Future[Version],
   140     val edits: List[Edit_Text],
   141     val result: Future[(List[Edit_Command], Version)])
   142   {
   143     val version: Future[Version] = result.map(_._2)
   144     def is_finished: Boolean = previous.is_finished && version.is_finished
   145   }
   146 
   147 
   148   /* history navigation */
   149 
   150   object History
   151   {
   152     val init = new History(List(Change.init))
   153   }
   154 
   155   // FIXME pruning, purging of state
   156   class History(val undo_list: List[Change])
   157   {
   158     require(!undo_list.isEmpty)
   159 
   160     def tip: Change = undo_list.head
   161     def +(change: Change): History = new History(change :: undo_list)
   162   }
   163 
   164 
   165 
   166   /** global state -- document structure, execution process, editing history **/
   167 
   168   abstract class Snapshot
   169   {
   170     val version: Version
   171     val node: Node
   172     val is_outdated: Boolean
   173     def lookup_command(id: Command_ID): Option[Command]
   174     def state(command: Command): Command.State
   175     def convert(i: Text.Offset): Text.Offset
   176     def convert(range: Text.Range): Text.Range
   177     def revert(i: Text.Offset): Text.Offset
   178     def revert(range: Text.Range): Text.Range
   179     def select_markup[A](range: Text.Range)(result: Markup_Tree.Select[A])
   180       : Stream[Text.Info[Option[A]]]
   181   }
   182 
   183   object State
   184   {
   185     class Fail(state: State) extends Exception
   186 
   187     val init = State().define_version(Version.init, Map()).assign(Version.init.id, Nil)._2
   188 
   189     case class Assignment(
   190       val assignment: Map[Command, Exec_ID],
   191       val is_finished: Boolean = false)
   192     {
   193       def get_finished: Map[Command, Exec_ID] = { require(is_finished); assignment }
   194       def assign(command_execs: List[(Command, Exec_ID)]): Assignment =
   195       {
   196         require(!is_finished)
   197         Assignment(assignment ++ command_execs, true)
   198       }
   199     }
   200   }
   201 
   202   case class State(
   203     val versions: Map[Version_ID, Version] = Map(),
   204     val commands: Map[Command_ID, Command.State] = Map(),
   205     val execs: Map[Exec_ID, (Command.State, Set[Version])] = Map(),
   206     val assignments: Map[Version, State.Assignment] = Map(),
   207     val disposed: Set[ID] = Set(),  // FIXME unused!?
   208     val history: History = History.init)
   209   {
   210     private def fail[A]: A = throw new State.Fail(this)
   211 
   212     def define_version(version: Version, former_assignment: Map[Command, Exec_ID]): State =
   213     {
   214       val id = version.id
   215       if (versions.isDefinedAt(id) || disposed(id)) fail
   216       copy(versions = versions + (id -> version),
   217         assignments = assignments + (version -> State.Assignment(former_assignment)))
   218     }
   219 
   220     def define_command(command: Command): State =
   221     {
   222       val id = command.id
   223       if (commands.isDefinedAt(id) || disposed(id)) fail
   224       copy(commands = commands + (id -> command.empty_state))
   225     }
   226 
   227     def lookup_command(id: Command_ID): Option[Command] = commands.get(id).map(_.command)
   228 
   229     def the_version(id: Version_ID): Version = versions.getOrElse(id, fail)
   230     def the_command(id: Command_ID): Command.State = commands.getOrElse(id, fail)
   231     def the_exec_state(id: Exec_ID): Command.State = execs.getOrElse(id, fail)._1
   232     def the_assignment(version: Version): State.Assignment = assignments.getOrElse(version, fail)
   233 
   234     def accumulate(id: ID, message: XML.Elem): (Command.State, State) =
   235       execs.get(id) match {
   236         case Some((st, occs)) =>
   237           val new_st = st.accumulate(message)
   238           (new_st, copy(execs = execs + (id -> (new_st, occs))))
   239         case None =>
   240           commands.get(id) match {
   241             case Some(st) =>
   242               val new_st = st.accumulate(message)
   243               (new_st, copy(commands = commands + (id -> new_st)))
   244             case None => fail
   245           }
   246       }
   247 
   248     def assign(id: Version_ID, edits: List[(Command_ID, Exec_ID)]): (List[Command], State) =
   249     {
   250       val version = the_version(id)
   251       val occs = Set(version)  // FIXME unused (!?)
   252 
   253       var new_execs = execs
   254       val assigned_execs =
   255         for ((cmd_id, exec_id) <- edits) yield {
   256           val st = the_command(cmd_id)
   257           if (new_execs.isDefinedAt(exec_id) || disposed(exec_id)) fail
   258           new_execs += (exec_id -> (st, occs))
   259           (st.command, exec_id)
   260         }
   261       val new_assignment = the_assignment(version).assign(assigned_execs)
   262       val new_state =
   263         copy(assignments = assignments + (version -> new_assignment), execs = new_execs)
   264       (assigned_execs.map(_._1), new_state)
   265     }
   266 
   267     def is_assigned(version: Version): Boolean =
   268       assignments.get(version) match {
   269         case Some(assgn) => assgn.is_finished
   270         case None => false
   271       }
   272 
   273     def extend_history(previous: Future[Version],
   274         edits: List[Edit_Text],
   275         result: Future[(List[Edit_Command], Version)]): (Change, State) =
   276     {
   277       val change = new Change(previous, edits, result)
   278       (change, copy(history = history + change))
   279     }
   280 
   281 
   282     // persistent user-view
   283     def snapshot(name: String, pending_edits: List[Text.Edit]): Snapshot =
   284     {
   285       val found_stable = history.undo_list.find(change =>
   286         change.is_finished && is_assigned(change.version.get_finished))
   287       require(found_stable.isDefined)
   288       val stable = found_stable.get
   289       val latest = history.undo_list.head
   290 
   291       // FIXME proper treatment of deleted nodes
   292       val edits =
   293         (pending_edits /: history.undo_list.takeWhile(_ != stable))((edits, change) =>
   294             (for ((a, Some(eds)) <- change.edits if a == name) yield eds).flatten ::: edits)
   295       lazy val reverse_edits = edits.reverse
   296 
   297       new Snapshot
   298       {
   299         val version = stable.version.get_finished
   300         val node = version.nodes(name)
   301         val is_outdated = !(pending_edits.isEmpty && latest == stable)
   302 
   303         def lookup_command(id: Command_ID): Option[Command] = State.this.lookup_command(id)
   304 
   305         def state(command: Command): Command.State =
   306           try { the_exec_state(the_assignment(version).get_finished.getOrElse(command, fail)) }
   307           catch { case _: State.Fail => command.empty_state }
   308 
   309         def convert(offset: Text.Offset) = (offset /: edits)((i, edit) => edit.convert(i))
   310         def revert(offset: Text.Offset) = (offset /: reverse_edits)((i, edit) => edit.revert(i))
   311         def convert(range: Text.Range) = (range /: edits)((r, edit) => edit.convert(r))
   312         def revert(range: Text.Range) = (range /: reverse_edits)((r, edit) => edit.revert(r))
   313 
   314         def select_markup[A](range: Text.Range)(result: Markup_Tree.Select[A])
   315           : Stream[Text.Info[Option[A]]] =
   316         {
   317           val former_range = revert(range)
   318           for {
   319             (command, command_start) <- node.command_range(former_range).toStream
   320             Text.Info(r0, x) <- state(command).markup.
   321               select((former_range - command_start).restrict(command.range)) {
   322                 case Text.Info(r0, info)
   323                 if result.isDefinedAt(Text.Info(convert(r0 + command_start), info)) =>
   324                   result(Text.Info(convert(r0 + command_start), info))
   325               }
   326           } yield Text.Info(convert(r0 + command_start), x)
   327         }
   328       }
   329     }
   330   }
   331 }
   332