Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.1

0.45.1 / src / canvas / history.lucb

#==============================================================================================
#
#   canvas/history - The undo and redo snapshots
#
#   DESCRIPTION:
#       Two kinds of snapshot, one stack. A pixel snapshot holds one layer's pixels (or its
#       mask's) from before an edit: strokes, fills, filters. A state snapshot holds the whole
#       document from before a change to what it is made of: the layer tree (sharing tiles),
#       the layers' records, the extent, the selection, the guides and the alpha channels
#       (sharing cells). Undo and redo swap a snapshot with
#       the document, so neither copies anything. Every snapshot names its step.
#
#==============================================================================================

extend Canvas:
    ## Make the next edit undo and redo together with the one before it, as
    ## one step: several layers moved at once.
    pub func join_next_edit():
        self.joining = true

    ## Make the next step its own even where it would continue the last (typing
    ## into the same text layer again): an edit session can then be taken back
    ## on its own with `undo` down to `step_serial`.
    pub func separate_next_step():
        self.separating = true

    ## The serial of the step Undo would take back (0: none): unchanged
    ## while nothing new is remembered.
    pub func step_serial() -> i64:
        return (i64)self.history[self.history_count - 1].serial if self.history_count > 0 else 0

    ## How many bytes of GPU tiles the undo history may hold beyond what the
    ## document shows (4 GiB by default): past it the oldest steps are dropped,
    ## though the last step always stays. The next step applies it.
    pub func set_history_limit(bytes: i64) -> !:
        if bytes < 0:
            error(invalid, "a history budget cannot be negative")
        self.history_budget = (u64)bytes

    pub func history_limit() -> i64:
        return (i64)self.history_budget

    ## How many steps undo can take back.
    pub func undo_steps() -> i64:
        return (i64)self.history_count

    ## Bytes of GPU memory in pixel tiles, across every open document with its
    ## history and selection: a figure for a memory readout.
    pub static func tile_memory() -> i64:
        return (i64)tiles_alive() * (i64)tile_memory_bytes

    pub func can_undo() -> bool:
        return self.history_count > 0

    pub func can_redo() -> bool:
        return self.future_count > 0

    ## Put back the pixels a layer (or its mask) had before the last edit.
    pub func undo() -> !:
        try self.require_open()
        try self.require_idle()
        if self.history_count == 0:
            error(invalid, "nothing to undo")
        let document = self.document else trap("history without a document")
        # An edit may have remembered several snapshots; they go back together.
        while self.history_count > 0:
            let entry = self.history[self.history_count - 1]
            self.history_count -= 1
            try push(&self.future, &self.future_count, try self.swap_in(document, entry))
            if not entry.joined:
                break

    ## Redo the last undone edit.
    pub func redo() -> !:
        try self.require_open()
        try self.require_idle()
        if self.future_count == 0:
            error(invalid, "nothing to redo")
        let document = self.document else trap("history without a document")
        var first = true
        while self.future_count > 0 and (first or self.future[self.future_count - 1].joined):
            first = false
            let entry = self.future[self.future_count - 1]
            self.future_count -= 1
            try push(&self.history, &self.history_count, try self.swap_in(document, entry))

    ## Record a layer's pixels before a change, as step `name`, dropping the
    ## redo trail and the oldest entries past the limit.
    func remember(layer: u64, tiles: Tiles, mask: bool = false, joined: bool = false, name: str = "Edit") -> !:
        var owned = tiles
        errdefer owned.destroy()
        try require_loaded(&self)
        # Pixels of a text layer changed as pixels (a move only moves it): it is
        # no longer text. The step holds the whole document, with the pixels
        # from before put back while it is taken, so undo brings the text back.
        if not mask and name != "Move":
            let index = self.index(layer) catch _:
                recover self.count
            if index < self.count and (self.records[index].typed or self.records[index].shaped):
                let document = self.document else trap("pixels changed without a document")
                var now = try document.take_tiles(layer, owned)
                try self.remember_state(name)
                var before = try document.take_tiles(layer, now)
                before.destroy()
                rasterize_type(&self, layer)
                rasterize_shape(&self, layer)
                return
        # Inside an edit that recorded the whole document, its step already holds these pixels.
        if self.edit_depth > 0 and self.edit_captured:
            owned.destroy()
            return
        self.make_room()
        let join = joined or (self.joining and self.history_count > 0)
        self.joining = false
        self.serial += 1
        try push(&self.history, &self.history_count, Snapshot(layer = layer, tiles = tiles, mask = mask, joined = join, name = name, serial = self.serial))
        try trim_history(&self)

    ## Record the whole document before a change to what it is made of, as
    ## step `name`. The same change to the same layer again (`layer` non-zero)
    ## right after is one step with it — an opacity slider dragged — and
    ## inside `begin_edit` nothing more is recorded. Nothing is kept before the
    ## document is drawn once.
    func remember_state(name: str, layer: u64 = 0) -> !:
        let document = self.document else return
        try require_loaded(&self)
        if self.edit_depth > 0 and self.history_count > 0:
            return
        if self.edit_depth == 0 and layer != 0 and self.future_count == 0 and self.history_count > 0:
            let top = self.history[self.history_count - 1]
            # Not into the step the document was saved at: the change after saving is its own.
            if top.state != none and top.layer == layer and top.name == name and top.serial != self.saved_version and not self.separating:
                return
        var tree = try document.capture()
        errdefer tree.destroy()
        let records = try copy_records(self.records, self.count)
        errdefer release_records(records, self.count)
        var channels = try self.channels.copy()
        errdefer channels.destroy()
        let state = try new DocumentState(tree = tree, records = records, count = self.count, next_id = self.next_id, guides = self.guides, channels = channels) in memory.heap
        errdefer free(state) in memory.heap
        self.make_room()
        let join = self.joining and self.history_count > 0
        self.joining = false
        self.separating = false
        self.serial += 1
        try push(&self.history, &self.history_count, Snapshot(layer = layer, tiles = Tiles(), mask = false, joined = join, state = state, name = name, serial = self.serial))
        try trim_history(&self)

    ## Drop the redo trail and, at the limit, the oldest step.
    func make_room():
        clear_snapshots(&self.future, &self.future_count)
        if self.history_count == 64:
            drop_oldest(&self)

    ## Put `entry`'s pixels or document in place, returning a snapshot of what
    ## was there, for the other stack.
    func swap_in(document: Document*, entry: Snapshot) -> Snapshot!:
        if let state = entry.state:
            document.exchange(&state.tree)
            let records = self.records
            self.records = state.records
            state.records = records
            let count = self.count
            self.count = state.count
            state.count = count
            let next_id = self.next_id
            self.next_id = state.next_id
            state.next_id = next_id
            let guides = self.guides
            self.guides = state.guides
            state.guides = guides
            let channels = self.channels
            self.channels = state.channels
            state.channels = channels
            # History keeps the cells alone, not their GPU tiles.
            state.channels.drop_gpu_tiles()
            self.extent_x = document.width()
            self.extent_y = document.height()
            return entry
        let current = try (document.take_mask(entry.layer, entry.tiles) if entry.mask else document.take_tiles(entry.layer, entry.tiles))
        return Snapshot(layer = entry.layer, tiles = current, mask = entry.mask, joined = entry.joined, name = entry.name, serial = entry.serial)

    ## Make everything until `end_edit` one step named `name`: a layer grouped
    ## with others, a picture placed.
    pub func begin_edit(name: str) -> !:
        try self.require_open()
        if self.edit_depth == 0:
            let before = self.serial
            try self.remember_state(name)
            self.edit_captured = self.serial != before
        self.edit_depth += 1

    pub func end_edit():
        if self.edit_depth > 0:
            self.edit_depth -= 1

    ## Whether the document differs from when it was last saved (or opened):
    ## undoing back to that point counts as unchanged.
    pub func modified() -> bool:
        let version = self.history[self.history_count - 1].serial if self.history_count > 0 else 0
        return version != self.saved_version

    ## The document is as saved now.
    pub func mark_saved():
        self.saved_version = self.history[self.history_count - 1].serial if self.history_count > 0 else 0

    ## The step Undo would take back, or "" when there is none; `redo_name` likewise.
    pub func undo_name() -> str:
        return self.history[self.history_count - 1].name if self.history_count > 0 else ""

    pub func redo_name() -> str:
        return self.future[self.future_count - 1].name if self.future_count > 0 else ""

    ## The steps Undo takes back one at a time, as a History panel lists them:
    ## how many, and each one's name, 0 the oldest (what `undo_name` says when
    ## it is the last). Snapshots taken together count once.
    pub func history_steps() -> i64:
        return (i64)step_starts(self.history, self.history_count, false, none)

    pub func history_step_name(index: i64) -> str:
        return step_name(self.history, self.history_count, false, index)

    ## The steps Redo brings back, 0 the next one.
    pub func future_steps() -> i64:
        return (i64)step_starts(self.future, self.future_count, true, none)

    pub func future_step_name(index: i64) -> str:
        return step_name(self.future, self.future_count, true, index)

## The document as a state snapshot keeps it: the tree, extent and selection,
## and the layers' records, the guides and the alpha channels beside them.
struct DocumentState:
    var tree: TreeState
    var records: Record[]
    var count: usize
    var next_id: u64
    var guides: Guides
    var channels: Channels

## A layer's pixels (or its mask's) at one moment, shared with whatever else
## holds them, or the whole document (`state`). A joined snapshot belongs to
## the same edit as the one before it: undo and redo take them together.
## `name` is the step's, as the Edit menu says it; `layer` also tells which
## layer a state snapshot's change was on, so repeated changes to it coalesce.
struct Snapshot:
    var layer: u64
    var tiles: Tiles
    var mask: bool
    var joined: bool = false
    var state: DocumentState*? = none
    var name: str = "Edit"
    ## Which step this is, for telling whether the document is as saved.
    var serial: u64 = 0

## Free what a snapshot holds.
func drop_snapshot(entry: Snapshot*):
    if let state = entry.state:
        state.tree.destroy()
        state.channels.destroy()
        release_records(state.records, state.count)
        free(state) in memory.heap
        entry.state = none
    else:
        entry.tiles.destroy()

## What the history may hold beyond the document by default: 4 GiB of tiles.
let default_history_budget: u64 = 4294967296

## GPU bytes of one tile: 256 by 256 half-float RGBA.
let tile_memory_bytes: u64 = 524288

## Drop the oldest step, and let what was joined to it start the oldest edit kept.
func drop_oldest(canvas: Canvas*):
    drop_snapshot(&canvas.history[0])
    for index in 1..<canvas.history_count:
        canvas.history[index - 1] = canvas.history[index]
    canvas.history_count -= 1
    if canvas.history_count > 0:
        canvas.history[0].joined = false

## Keep the history within its budget: while the tiles alive past those the
## document shows take more than `history_budget`, drop the oldest step. The
## newest step always stays, so the last change can be undone. Tiles are
## counted across every open document, which only makes this cautious.
func trim_history(canvas: Canvas*) -> !:
    if (u64)tiles_alive() * tile_memory_bytes <= canvas.history_budget:
        return
    let document = canvas.document else return
    let shown = try shown_tiles(document)
    while canvas.history_count > 1:
        let alive = (u64)tiles_alive()
        let beyond = alive - shown if alive > shown else 0
        if beyond * tile_memory_bytes <= canvas.history_budget:
            return
        drop_oldest(canvas)

## How many different tiles the document's layers and masks show.
func shown_tiles(document: Document*) -> u64!:
    var seen = try StampSet.create(4096)
    defer seen.destroy()
    for layer in document.layers():
        try count_layer_tiles(layer, &seen)
    return (u64)seen.count

func count_layer_tiles(layer: Layer*, seen: StampSet*) -> !:
    if let tiles = layer.tiles():
        try count_cells(tiles, seen)
    if let mask = layer.mask_tiles():
        try count_cells(mask, seen)
    for child in layer.layers():
        try count_layer_tiles(child, seen)

func count_cells(tiles: const Tiles*, seen: StampSet*) -> !:
    for row in 0..<tiles.rows():
        for column in 0..<tiles.columns():
            let stamp = tiles.stamp(column, row)
            if stamp != 0:
                try seen.add(stamp)

## A set of tile stamps (never 0), open addressing, grown at half full.
struct StampSet:
    var slots: u64[]
    var count: usize

    static func create(capacity: usize) -> StampSet!:
        let slots = try new u64[capacity] --- in memory.heap
        memory.set(u8[]((u8*)slots.data, slots.length * 8), 0)
        return StampSet(slots = slots, count = 0)

    func add(stamp: u64) -> !:
        if (self.count + 1) * 2 > self.slots.length:
            let old = self.slots
            let grown = try new u64[old.length * 2] --- in memory.heap
            memory.set(u8[]((u8*)grown.data, grown.length * 8), 0)
            self.slots = grown
            self.count = 0
            for value in old:
                if value != 0:
                    self.insert(value)
            free(old) in memory.heap
        self.insert(stamp)

    func insert(stamp: u64):
        let mask = self.slots.length - 1
        var at = (usize)((stamp *% 0x9e3779b97f4a7c15) >> 20) & mask
        while self.slots[at] != 0:
            if self.slots[at] == stamp:
                return
            at = (at + 1) & mask
        self.slots[at] = stamp
        self.count += 1

    func destroy():
        free(self.slots) in memory.heap

## Append `entry` to a snapshot list, growing it.
func push(list: Snapshot[]*, count: usize*, entry: Snapshot) -> !:
    if *count == list.length:
        let capacity = 16 if list.length == 0 else list.length * 2
        let grown = try new Snapshot[capacity] --- in memory.heap
        if *count > 0:
            memory.copy(grown, *list, *count)
        if list.length > 0:
            free(*list) in memory.heap
        *list = grown
    (*list)[*count] = entry
    *count += 1

## Destroy every snapshot in a list and empty it.
func clear_snapshots(list: Snapshot[]*, count: usize*):
    for index in 0..<*count:
        drop_snapshot(&(*list)[index])
    *count = 0

## A copy of the first `count` records, names and all, for a state snapshot
## (pictures waiting to be bound are not kept: a bound document has none).
func copy_records(records: const Record[], count: usize) -> Record[]!:
    let copies = try new Record[count if count > 0 else 1] --- in memory.heap
    # On failure the records copied so far go, and the one being copied lets go
    # of what it took.
    var copied: usize = 0
    errdefer release_records(copies, copied)
    for index in 0..<count:
        var name: str = ""
        with memory.heap:
            name = try strings.copy(records[index].name)
        errdefer strings.release(name)
        copies[index] = records[index]
        copies[index].name = name
        copy_type(&copies[index]) catch failure:
            copies[index].typed = false
            error(failure.code, failure.message)
        # On failure the copy holds no elements, and its text is its own to free.
        errdefer release_type(&copies[index])
        try copy_elements(&copies[index])
        copies[index].picture = none
        copies[index].mask_picture = none
        copied += 1
    return copies

## Free a records copy and the first `count` names in it.
func release_records(records: Record[], count: usize):
    for index in 0..<count:
        strings.release(records[index].name)
        release_type(&records[index])
        release_elements(&records[index])
    free(records) in memory.heap

## The user steps of a history stack, `count` entries of `entries`: on the undo
## stack (`future` false) a step is an entry not joined with those joined above
## it, oldest first; on the redo stack it is the top entry with those joined
## below it, next first. How many there are; with `index`, the entry that
## names step `index` (the one Undo's menu would name) goes into `named`.
func step_starts(entries: const Snapshot[], count: usize, future: bool, index: i64?, named: usize*? = none) -> usize:
    var steps: usize = 0
    if not future:
        var at: usize = 0
        while at < count:
            # The step runs up through every joined entry above its first.
            var top = at
            while top + 1 < count and entries[top + 1].joined:
                top += 1
            if let wanted = index:
                if wanted == (i64)steps:
                    if let out = named: *out = top
            steps += 1
            at = top + 1
        return steps
    var at = count
    while at > 0:
        # From the next redo down through the joined entries below it.
        var bottom = at - 1
        while bottom > 0 and entries[bottom - 1].joined:
            bottom -= 1
        if let wanted = index:
            if wanted == (i64)steps:
                if let out = named: *out = bottom
        steps += 1
        at = bottom
    return steps

## The name of step `index` of a history stack, "" past its end.
func step_name(entries: const Snapshot[], count: usize, future: bool, index: i64) -> str:
    var named = count
    _ = step_starts(entries, count, future, index, &named)
    return entries[named].name if named < count else ""