#
# Created by Boyd Multerer on 2017-05-06.
# Copyright © 2017 Kry10 Limited. All rights reserved.
#
defmodule Scenic.Graph do
@moduledoc """
Please see [`Graph Overview`](overview_graph.html) for a high-level description.
## What is a Graph
There are many types of graphs in the field of Computer Science. There are graphs that
show data to a user. There are graphs that give access to databases. Graphs that link
people to a social network.
In Scenic, a Graph is a graph in same way that the DOM in HTML is a graph. It is a
hierarchical tree of data that describes a set of things to draw on the screen.
You build a graph by appending primitives (individual things to draw) to the current
node in the tree. Nodes are represented by `Scenic.Primitive.Group`.
The following example builds a simple graph that displays some text, creates a group,
then adds more text and a rounded rectangle to it.
```elixir
@graph Scenic.Graph.build()
|> text( "This is some text", translate: {20, 20} )
|> group( fn(graph) ->
graph
|> text( "This text is in a group", translate: {200, 24} )
|> rounded_rectangle( {400, 30}, stroke: {2, :blue})
end, translate: {20, 100}, text_align: :center)
```
There is a fair amount going on in the example above. The first line builds an empty
graph with only one group as the root node.
```elixir
@graph Scenic.Graph.build()
```
By assigning it to the
compile directive `@group`, we know that this group will be built once at compile
time and will be very fast to access later during runtime. You could also do this
at runtime, in your init function for example.
The empty graph that is returned from `build()` is then passed to
```elixir
|> text( "This is some text", translate: {20, 20} )
```
This adds a text primitive to the root group. The graph returned from that call is then
passed again into
```elixir
|> group( fn(graph) ->
graph
|> text( "This text is in a group", translate: {200, 24} )
|> rounded_rectangle( {400, 30}, stroke: {2, :blue})
end, translate: {20, 100}, text_align: :center)
```
This creates a new group which is filled with several other primitives.
Notice that the anonymous group "builder" function receives a graph as its only parameter.
This is the same graph that we are building, except that it has a marker indicating
that new primitives added to it are inserted into the new group instead of the
root of the graph.
Finally, when the group is finished, a translation matrix and a `:text_align` style
are added to it. These properties are _inherited_ by the primitives in the group.
## Inheritance
An important concept to understand is that both [styles](overview_styles.html) and
[transforms](overview_styles.html) are inherited down the graph. This means that if
you apply a style or transform to any group (including the root), then all primitives
contained by that group will have those properties applied to them too. This is true
even if the primitive is nested in several groups at the same time.
```elixir
@graph Scenic.Graph.build(font: :roboto_mono)
|> text( "This text inherits the font", translate: {20, 20} )
|> group( fn(graph) ->
graph
|> text( "This text also inherits the font", translate: {200, 24} )
|> text( "This text overrides the font", font: :roboto )
end, translate: {20, 100}, text_align: :center)
```
Transforms, such as translate, rotate, scale, also inherit down the graph, but do
so slightly differently than the styles. With a style, when you set a specific value
on a primitive, that overrides the inherited value of the same type.
With a transform, the values multiply together. This allows you to position items
within a group relative to the origin {0,0}, then move the group as a whole, keeping
the interior positions unchanged.
Styles, however, are NOT inherited by components even though transforms are.
## Modifying a Graph
Scenic was written specifically for Erlang/Elixir, which is a functional programming
model with immutable data.
As such, once you make a graph, it stays in memory unchanged - until you transform it
via `Graph.modify/3`. Technically you never change it (that's the immutable part),
instead Graph.modify returns a new graph with different data in it.
[Graph.modify/3](Scenic.Graph.html#modify/3) is the single Graph function that you
will use the most.
For example, lets go back to our graph with the two text items in it.
```elixir
@graph Graph.build(font: :roboto, font_size: 24, rotate: 0.4)
|> text("Hello World", translate: {300, 300}, id: :small_text)
|> text("Bigger Hello", font_size: 40, scale: 1.5, id: :big_text)
```
This time, we've assigned ids to both of the text primitives. This makes it easy to
find and modify that primitive in the graph.
```elixir
graph =
@graph
|> Graph.modify( :small_text, &text(&1, "Smaller Hello", font_size: 16))
|> Graph.modify( :big_text, &text(&1, "Bigger Hello", font_size: 60))
```
Notice that the graph is modified multiple times in the pipeline. The `push_graph/1`
function is relatively heavy when the graph references other scenes. The recommended
pattern is to make multiple changes to the graph .
## Accessing Primitives
When using a Graph, it is extremely common to access and modify primitives. The way
you do this is by putting an id on the primitives you care about in a graph.
```elixir
@graph Graph.build()
|> text("small text", id: :small_text)
|> text("bit text", id: :big_text)
```
When you get primitives, or modify a graph, you specify them by id. This happens
quickly, but at a cost of using a little memory. If you aren't going to access
a primitive, then don't assign an id to them.
One interesting note: There is nothing saying you have to use an atom as the id.
In fact you can use any Erlang term you want. This can be very powerful, especially
when used to identify components...
"""
alias Scenic.Primitive
alias Scenic.Primitive.Group
# make reserved uids, 3 or shorter to avoid potential conflicts
@root_uid 0
@default_max_depth 128
@root_id :_root_
defstruct primitives: %{}, ids: %{}, next_uid: 1, add_to: 0, animations: []
@type t :: %__MODULE__{
primitives: map,
ids: map,
next_uid: pos_integer,
add_to: non_neg_integer
}
@type bounds :: {left :: number, top :: number, right :: number, bottom :: number}
@type deferred :: (t -> t)
# ===========================================================================
# TODO: define a policy error here - not found or something like that
defmodule Error do
@moduledoc false
defexception message: "Graph was unable to perform the operation",
# TODO: expecting more appropriate messages when raising this
primitive: nil,
style: nil
end
@err_msg_depth "Graph too deep. Possible circular reference!"
@err_msg_depth_option "The :max_depth option must be a positive integer"
@err_msg_put "Graph.put can only update existing items."
@err_msg_get_id_one "Graph.get! expected to find one and only one element"
# ============================================================================
# build a new graph, starting with the given element
@doc """
Builds and returns an empty graph.
Just like any primitive, you can pass in an option list of styles and transforms.
These will be applied to the otherwise empty root group in the new graph.
"""
@spec build(opts :: keyword) :: t()
def build(opts \\ []) do
[]
|> Group.build(Keyword.put(opts, :id, @root_id))
|> new()
|> set_id(opts[:id])
|> set_max_depth(opts[:max_depth])
end
# ============================================================================
# add a pre-built primitive
@doc """
Add a pre-built primitive to the current group in the graph.
This is usually called during graph construction. When a new Group primitive
is added to a Graph, it marks the new group as the current one before calling the group's
builder function. This is what allows you to add primitives to the correct place
in the new Group.
Note: All primitives added to a group are appended to the draw order.
"""
@spec add(graph :: t(), primitive :: Primitive.t()) :: t()
def add(graph, primitive)
def add(%__MODULE__{add_to: puid} = g, %Primitive{} = p) do
{graph, _uid} = insert_at({g, puid}, -1, p)
graph
end
# build and add new primitives
@doc """
Build and add a primitive to the current group in the graph.
This is usually called during graph construction. When a new Group primitive
is added to a Graph, it marks the new group as the current one before calling the group's
builder function. This is what allows you to add primitives to the correct place
in the new Group.
Note: All primitives added to a group are appended to the draw order.
"""
@spec add(graph :: t(), module :: atom, data :: any, opts :: keyword) :: t()
def add(graph, primitive_module, primitive_data, opts \\ [])
def add(%__MODULE__{add_to: puid} = g, Group, builder, opts) when is_function(builder, 1) do
p = Group.build([], opts)
{graph, uid} = insert_at({g, puid}, -1, p, opts)
graph
# set the new group as the add_to target
|> Map.put(:add_to, uid)
# call the group builder callback
|> builder.()
# restore the add_to to puid
|> Map.put(:add_to, puid)
end
def add(%__MODULE__{add_to: puid} = g, mod, data, opts) when is_atom(mod) do
p = mod.build(data, opts)
{graph, _uid} = insert_at({g, puid}, -1, p, opts)
graph
end
# ============================================================================
# delete a primitive/s from a graph
@doc """
Permanently delete a primitive from a group by id.
This will remove a primitive (or many if they have the same id) from a graph. It
then returns the modified graph.
If you delete a group from a graph, then all primitives contained by that
group are deleted as well.
"""
@spec delete(graph :: t(), id :: any) :: t()
def delete(%__MODULE__{primitives: primitives, ids: ids} = graph, id) do
# resolve the id into a list of uids
uids = Map.get(ids, id, [])
# delete each uid. Keep track of the primitives map, and build
# list of descendands if we're deleting a group
{primitives, descendants} =
Enum.reduce(uids, {primitives, []}, fn uid, {prims, removes} ->
# get the uid of the parent group
%Primitive{parent_uid: puid, module: mod, data: data} = prims[uid]
p =
prims[puid]
|> remove_reference_from_parent(prims, uid, puid)
# delete the primitive itself
|> Map.delete(uid)
{p, removes ++ children_to_remove(p, mod, data)}
end)
# delete the ids
ids = Map.delete(ids, id)
# if there was a group involved, remove that group's children
{primitives, ids} = remove_group_children(descendants, primitives, ids)
# rebuild an updated graph
graph
|> Map.put(:primitives, primitives)
|> Map.put(:ids, ids)
end
# If the thing we're deleting is a group, find all descendants of the
# group so they can also be deleted.
defp children_to_remove(prims, Group, children) do
([children] ++
Enum.reduce(children, [], fn child, acc ->
case prims[child].module do
Group -> acc ++ children_to_remove(prims, prims[child].module, prims[child].data)
_ -> acc
end
end))
|> List.flatten()
end
defp children_to_remove(_prims, _, _children), do: []
# Remove all the descendants of the group that was just deleted.
defp remove_group_children(children, prims, ids) do
Enum.reduce(children, {prims, ids}, fn child, {prims, ids} ->
id = Map.get(prims[child], :id, nil)
{Map.delete(prims, child), Map.delete(ids, id)}
end)
end
# no parent
defp remove_reference_from_parent(-1, prims, _uid, _puid), do: prims
defp remove_reference_from_parent(
%Primitive{module: Group, data: children} = p,
prims,
uid,
puid
) do
children = Enum.reject(children, fn cuid -> cuid == uid end)
Map.put(prims, puid, %{p | data: children})
end
# ============================================================================
@doc """
Add to a specified group in a graph.
Similar to adding a group during graph construction, the `add_to` function accepts
a builder function that adds to a graph under the identified group.
Primitives with the `id` that are not groups are ignored.
If multiple groups have the given `id`, then the builder is run against each of them.
"""
def add_to(%__MODULE__{primitives: prims} = graph, id, builder) when is_function(builder, 1) do
# resolve the id into a list of uids
graph
|> resolve_id(id)
|> Enum.reduce(graph, fn uid, g ->
case prims[uid] do
%Primitive{module: Group} ->
g
|> Map.put(:add_to, uid)
|> builder.()
|> case do
%__MODULE__{} = g -> Map.put(g, :add_to, 0)
_ -> raise Error, message: "Group.add_to builder must return a valid graph"
end
_ ->
g
end
end)
end
# ============================================================================
# put an element by uid - internal use
defp put_by_uid(graph, uid, primitive)
defp put_by_uid(%__MODULE__{primitives: primitives} = graph, uid, primitive)
when is_integer(uid) do
case get_by_uid(graph, uid) do
nil ->
raise Error, message: @err_msg_put
_ ->
Map.put(
graph,
:primitives,
Map.put(primitives, uid, primitive)
)
end
end
# new
defp new(root) do
%__MODULE__{
primitives: %{@root_uid => root},
# pre-map the root
ids: %{@root_id => [0]}
}
end
# Set Graph ID
defp set_id(%__MODULE__{} = graph, nil), do: graph
defp set_id(%__MODULE__{} = graph, id), do: map_id_to_uid(graph, id, @root_uid)
# Set Graph max depth
defp set_max_depth(%__MODULE__{} = graph, nil), do: graph
defp set_max_depth(%__MODULE__{} = graph, max) when is_integer(max) and max > 0,
do: Map.put(graph, :max_depth, max)
defp set_max_depth(_, _), do: raise(Error, message: @err_msg_depth_option)
# ============================================================================
# create an entry in the ids
defp map_id_to_uid(graph, id, uid)
defp map_id_to_uid(%__MODULE__{ids: ids} = graph, id, uid) when is_integer(uid) do
Map.put(
graph,
:ids,
do_map_id_to_uid(ids, id, uid)
)
end
defp do_map_id_to_uid(%{} = ids, id, uid) when is_integer(uid) do
uid_list = Enum.uniq([uid | Map.get(ids, id, [])])
Map.put(ids, id, uid_list)
end
# ============================================================================
defp resolve_id(graph, id)
defp resolve_id(%__MODULE__{ids: ids}, id) do
Map.get(ids, id, [])
end
# ============================================================================
# --------------------------------------------------------
# count all the nodes in a graph.
@doc """
Returns a count of all the primitives in a graph.
The root Group counts as a primitive, so an empty graph should have a count
of 1.
"""
@spec count(graph :: t()) :: integer
def count(graph)
def count(%__MODULE__{} = graph) do
do_reduce(graph, 0, 0, fn _, acc -> acc + 1 end)
end
# --------------------------------------------------------
# count the nodes associated with an id.
@doc """
Returns a count of all the primitives in a graph with a specific id.
"""
@spec count(graph :: t(), id :: any) :: integer
def count(graph, id)
def count(%__MODULE__{ids: ids}, id) do
ids
|> Map.get(id, [])
|> Enum.count()
end
# ============================================================================
# get an element by uid. Used internally
defp get_by_uid(graph, uid, default \\ nil)
defp get_by_uid(%__MODULE__{primitives: primitives}, uid, default) when is_integer(uid) do
Map.get(primitives, uid, default)
end
# --------------------------------------------------------
# get an element by uid. Raise error if not there
defp get_by_uid!(graph, uid)
defp get_by_uid!(%__MODULE__{primitives: primitives}, uid) do
Map.fetch!(primitives, uid)
end
# ============================================================================
# get a list of primitives by id
@doc """
Returns a list of primitives from a graph with a specific id.
"""
@spec get(graph :: t(), id :: any) :: list(Primitive.t())
def get(%__MODULE__{} = graph, id) do
graph
|> resolve_id(id)
|> Enum.reduce([], fn uid, acc -> [get_by_uid(graph, uid) | acc] end)
|> Enum.reverse()
end
# --------------------------------------------------------
# get a single primitive by id. Raise error if it finds any count other than one
@doc """
Returns a single primitive from a graph with a specific id.
This will raise an error if either none or multiple primitives are found with
the specified id.
"""
@spec get!(graph :: t(), id :: any) :: Primitive.t()
def get!(%__MODULE__{} = graph, id) do
case resolve_id(graph, id) do
[uid] -> get_by_uid(graph, uid)
_ -> raise Error, message: @err_msg_get_id_one
end
end
# ============================================================================
# insert an element into the graph under the given parent
# returns the uid and transformed graph with the added element
# {graph, uid}
# NOTE: not sure this will stay private. May need to expose if I need to
# bring back templates
defp insert_at(graph_and_parent, index, element, opts \\ [])
# --------------------------------------------------------
# main version - force it to be a new item via -1 parent id
defp insert_at(
{%__MODULE__{primitives: primitives} = graph, parent_uid},
index,
%Primitive{} = primitive,
_opts
)
when is_integer(index) do
# uid for the new item
uid = next_uid = graph.next_uid
# prepare the primitive
primitive = Map.put(primitive, :parent_uid, parent_uid)
# add the element to the primitives map, setting parent_uid into place
primitives = Map.put(primitives, uid, primitive)
graph = Map.put(graph, :primitives, primitives)
# if a parent is requested, reference the element from the parent at the [sic]right/correct position
graph =
case parent_uid do
-1 ->
graph
puid ->
p_map = graph.primitives
p_map
|> Map.get(puid)
|> Group.insert_at(index, uid)
|> (&Map.put(p_map, puid, &1)).()
|> (&Map.put(graph, :primitives, &1)).()
end
# if the incoming primitive has an id set on it, map it to the uid
graph =
case Map.get(primitive, :id) do
nil -> graph
id -> map_id_to_uid(graph, id, uid)
end
# increment the next uid and gen the completed graph
{Map.put(graph, :next_uid, next_uid + 1), uid}
end
# ============================================================================
@doc """
Find one or more primitives in a graph via a filter function.
Pass in a function that accepts a primitive and returns a boolean.
Returns a list of tuples containing the matching id at the primitive.
`[{id, primitive}]`
__Warning:__ This function crawls the entire graph and is thus slower than
accessing items via a fully-specified id.
"""
@spec find(graph :: t(), (any -> as_boolean(term()))) :: list({any, Primitive.t()})
def find(graph, finder)
# pass in an atom based id, and it will transform all mapped uids
def find(%__MODULE__{} = graph, finder) when is_function(finder, 1) do
reduce(graph, [], fn p, acc ->
Map.get(p, :id)
|> finder.()
|> case do
true -> [p | acc]
false -> acc
end
end)
|> Enum.reverse()
end
# --------------------------------------------------------
# transform a single primitive by uid
# pass in a list of uids to transform
defp modify_by_uid(graph, uid, action) when is_integer(uid) and is_function(action, 1) do
case get_by_uid(graph, uid) do
# not found - do nothing
nil ->
graph
# transform
p_original ->
case action.(p_original) do
# no change. do nothing
^p_original -> graph
# changed. record it
%Primitive{} = p_modified -> put_by_uid(graph, uid, p_modified)
_ -> raise Error, message: "Action must return a valid primitive"
end
end
end
@doc """
Modify one or more primitives in a graph.
Retrieves the primitive (or primitives) specified by id and passes them to
a callback function. The result of the callback function is stored as the new
version of that primitive in the graph.
If multiple primitives match the specified id, then each is passed, in turn,
to the callback function.
The id can be either
* a term to match against (fast)
* a filter function that returns a boolean (slower)
Examples:
graph
|> Graph.modify( :explicit_id, &text("Updated Text 1") )
|> Graph.modify( {:id, 123}, &text("Updated Text 2") )
|> Graph.modify( &match?({:id,_},&1), &text("Updated Text 3") )
"""
@spec modify(
graph :: t(),
id :: any | (any -> as_boolean(term())),
action :: (any -> Primitive.t())
) :: t()
def modify(graph, id, action)
# pass in a finder function
def modify(%__MODULE__{} = graph, finder, action) when is_function(finder, 1) do
graph
|> find(finder)
|> Enum.map(fn %{id: id} -> id end)
|> Enum.uniq()
|> Enum.reduce(graph, &modify(&2, &1, action))
end
# pass in generic term id
def modify(%__MODULE__{} = graph, id, action) do
graph
|> resolve_id(id)
|> Enum.reduce(graph, &modify_by_uid(&2, &1, action))
end
# ============================================================================
# map a graph via traversal from the root node
@doc """
Map all primitives in a graph into a new graph.
Crawls through the entire graph, passing each primitive to the callback function.
The result of the callback replaces that primitive in the graph. The updated
graph is returned.
"""
@spec map(graph :: t(), action :: function) :: t()
def map(%__MODULE__{} = graph, action) when is_function(action, 1) do
do_map(graph, @root_uid, action)
end
# ============================================================================
@doc """
Map all primitives in a graph that match a specified id into a new graph.
Crawls through the entire graph, passing each primitive to the callback function.
The result of the callback replaces that primitive in the graph. The updated
graph is returned.
This is so similar to the modify function that it may be deprecated in the future.
For now I recommend you use `Graph.modify/3` instead of this.
"""
@spec map(graph :: t(), id :: any, action :: function) :: t()
def map(%__MODULE__{} = graph, id, action) when is_function(action, 1) do
# resolve the id into a list of uids
uids = resolve_id(graph, id)
# map those elements via reduction
Enum.reduce(uids, graph, fn uid, acc ->
# retrieve and map this node
acc
|> get_by_uid!(uid)
|> action.()
|> (&put_by_uid(acc, uid, &1)).()
end)
end
# --------------------------------------------------------
# map a graph via traversal starting at the node named by uid
defp do_map(graph, uid, action, depth_remaining \\ nil)
defp do_map(graph, uid, action, nil) do
max_depth = Map.get(graph, :max_depth, @default_max_depth)
do_map(graph, uid, action, max_depth)
end
defp do_map(_, _, _, 0), do: raise(Error, message: @err_msg_depth)
defp do_map(graph, uid, action, depth_remaining) do
# retrieve this node
primitive = get_by_uid!(graph, uid)
# retrieve and map this node
graph =
primitive
|> action.()
|> (&put_by_uid(graph, uid, &1)).()
# if this is a group, map its children
case primitive.module do
Group ->
# map its children by reducing the graph
Enum.reduce(Primitive.get(primitive), graph, fn uid, acc ->
do_map(acc, uid, action, depth_remaining - 1)
end)
# do nothing
_ ->
graph
end
end
# ============================================================================
@doc """
Invokes action for each primitive in the graph with the accumulator.
Iterates over all primitives in a graph, passing each into the callback function
with an accumulator. The return value of the callback is the new accumulator.
This is extremely similar in behaviour to Elixir's Enum.reduce function, except
that it understands how to navigate the tree structure of a Graph.
"""
# reduce a graph via traversal from the root node
@spec reduce(graph :: t(), acc :: any, action :: function) :: any
def reduce(%__MODULE__{} = graph, acc, action) when is_function(action, 2) do
do_reduce(graph, @root_uid, acc, action)
end
# ============================================================================
@doc """
Invokes action for each primitive that matches an id in the graph with the accumulator.
Iterates over all primitives that match a specified id, passing each into the callback
function with an accumulator.
This is extremely similar in behaviour to Elixir's Enum.reduce function, except
that it understands how to navigate the tree structure of a Graph.
"""
@spec reduce(graph :: t(), id :: any, acc :: any, action :: function) :: any
def reduce(%__MODULE__{} = graph, id, acc, action) when is_function(action, 2) do
# resolve the id into a list of uids
uids = resolve_id(graph, id)
# reduce on that list of uids
Enum.reduce(uids, acc, fn uid, acc ->
graph
|> get_by_uid!(uid)
|> action.(acc)
end)
end
# --------------------------------------------------------
# do_reduce is where max_depth is honored
defp do_reduce(graph, uid, acc, action, depth_remaining \\ nil)
defp do_reduce(graph, uid, acc, action, nil) do
max_depth = Map.get(graph, :max_depth, @default_max_depth)
do_reduce(graph, uid, acc, action, max_depth)
end
defp do_reduce(_, _, _, _, 0), do: raise(Error, message: @err_msg_depth)
defp do_reduce(graph, uid, acc, action, depth_remaining) when depth_remaining > 0 do
# retrieve this node
primitive = get_by_uid!(graph, uid)
# if this is a group, reduce its children
acc =
case primitive.module do
Group ->
Enum.reduce(Primitive.get(primitive), acc, fn uid, acc ->
do_reduce(graph, uid, acc, action, depth_remaining - 1)
end)
# do nothing
_ ->
acc
end
# reduce the node itself, returns the final accumulator
action.(primitive, acc)
end
# ============================================================================
@doc false
@spec style_stack(graph :: t(), uid :: integer) :: map
def style_stack(%__MODULE__{primitives: p_map} = graph, uid) when is_integer(uid) do
# get the target primitive
case p_map[uid] do
nil ->
%{}
%{parent_uid: -1} = p ->
Primitive.get_styles(p)
%{parent_uid: puid} = p ->
# merge the local styles into the parent styles
graph
|> style_stack(puid)
|> Map.merge(Primitive.get_styles(p))
end
end
# ============================================================================
# --------------------------------------------------------
@doc """
Compile a graph into a script.
"""
@spec compile(graph :: Scenic.Graph.t()) :: {:ok, Scenic.Script.t()}
defdelegate compile(graph), to: Scenic.Graph.Compiler
# --------------------------------------------------------
@doc """
Compute the bounding box that contains the graph.
Returns `{left, right, top, bottom}` or `nil` if the graph is empty.
"""
@spec bounds(graph :: t()) :: Scenic.Graph.bounds() | nil
defdelegate bounds(graph), to: Scenic.Graph.Bounds, as: :compute
end
