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