defmodule Spek do
@moduledoc """
Spek is a boolean expression engine for Elixir.
It allows you to model, optimize, and evaluate rules using composable
expressions.
This module contains all expression builder, evaluation, and optimization
functions. Please refer to the readme for details.
## Example
Given this check module:
defmodule DeviceChecks do
import Spek.Macros
defcheck device_online(device, reason: :device_offline) do
device.online?
end
defcheck battery_above_20(device, reason: :battery_too_low) do
device.battery_level > 20
end
defcheck charging(device) do
device.charging?
end
defcheck low_power_mode_enabled(device) do
device.low_power_mode?
end
end
We can compose, optimize, and evaluate rules like this:
iex> import Spek
iex> battery_safe =
...> all_of([
...> DeviceChecks.device_online_check(),
...> DeviceChecks.battery_above_20_check()
...> ])
iex> charging_safe =
...> all_of([
...> DeviceChecks.device_online_check(),
...> DeviceChecks.charging_check()
...> ])
iex> rule =
...> any_of([
...> battery_safe,
...> charging_safe,
...> DeviceChecks.low_power_mode_enabled_check()
...> ])
%Spek.AnyOf{
children: [
%Spek.AllOf{
children: [
%Spek.Check{
module: DeviceChecks,
fun: :device_online,
args: [:ctx]
},
%Spek.Check{
module: DeviceChecks,
fun: :battery_above_20,
args: [:ctx]
}
]
},
%Spek.AllOf{
children: [
%Spek.Check{
module: DeviceChecks,
fun: :device_online,
args: [:ctx]
},
%Spek.Check{
module: DeviceChecks,
fun: :charging,
args: [:ctx]
}
]
},
%Spek.Check{
module: DeviceChecks,
fun: :low_power_mode_enabled,
args: [:ctx]
}
]
}
iex> rule = optimize(rule)
%Spek.AnyOf{
children: [
%Spek.AllOf{
children: [
%Spek.Check{
module: DeviceChecks,
fun: :device_online,
args: [:ctx]
},
%Spek.AnyOf{
children: [
%Spek.Check{
module: DeviceChecks,
fun: :battery_above_20,
args: [:ctx]
},
%Spek.Check{
module: DeviceChecks,
fun: :charging,
args: [:ctx]
}
]
}
]
},
%Spek.Check{
module: DeviceChecks,
fun: :low_power_mode_enabled,
args: [:ctx]
}
]
}
iex> device = %{
...> online?: true,
...> battery_level: 12,
...> charging?: false,
...> low_power_mode?: false
...> }
iex> Spek.eval?(rule, device)
false
iex> device = %{
...> online?: false,
...> battery_level: 25,
...> charging?: false,
...> low_power_mode?: false
...> }
iex> Spek.eval_tree(rule, device)
{
:error,
%Spek.EvaluationError{
expression: %Spek.AnyOf{
children: [
%Spek.AllOf{
satisfied?: false,
children: [
%Spek.Check{
module: DeviceChecks,
fun: :device_online,
args: [:ctx],
result: {:error, :device_offline},
satisfied?: false
}
]
},
%Spek.Check{
module: DeviceChecks,
fun: :low_power_mode_enabled,
args: [:ctx],
result: {:error, :failed},
satisfied?: false
}
],
satisfied?: false
},
message: "rule evaluation failed"
}
}
"""
alias Spek.AllOf
alias Spek.AnyOf
alias Spek.Check
alias Spek.EvaluationError
alias Spek.Literal
alias Spek.Not
@typedoc """
A boolean expression tree.
"""
@type expression :: AllOf.t() | AnyOf.t() | Check.t() | Literal.t() | Not.t()
@typedoc """
The evaluation context as passed to the evaluation functions.
"""
@type context :: term
@typedoc """
An expression result value that results in a successful evaluation.
"""
@type truthy :: true | :ok | {:ok, term}
@typedoc """
An expression result value that results in a failed evaluation.
"""
@type falsy :: false | :error | {:error, term}
@typedoc """
The result of an expression evaluation.
"""
@type result :: truthy | falsy
## Builders
@doc """
Builds an expression that requires all children to be true.
## Example
iex> all_of([
...> check(MyModule, :session_active, []),
...> check(MyModule, :permissions_valid, [])
...> ])
%Spek.AllOf{
children: [
%Spek.Check{module: MyModule, fun: :session_active, args: []},
%Spek.Check{module: MyModule, fun: :permissions_valid, args: []}
]
}
"""
@doc type: :builder
@spec all_of([expression]) :: AllOf.t()
def all_of(children) when is_list(children) do
%AllOf{children: children}
end
@doc """
Builds an expression that requires both children to be true.
## Example
iex> all_of(
...> check(RenderingChecks, :color_profile_valid, []),
...> check(RenderingChecks, :frame_rate_supported, [])
...> )
%Spek.AllOf{
children: [
%Spek.Check{module: RenderingChecks, fun: :color_profile_valid, args: []},
%Spek.Check{module: RenderingChecks, fun: :frame_rate_supported, args: []}
]
}
"""
@doc type: :builder
@spec all_of(expression, expression) :: AllOf.t()
def all_of(a, b) do
%AllOf{children: [a, b]}
end
@doc """
Builds an expression that requires at least one child to be true.
## Example
iex> any_of([
...> check(AudioPipelineChecks, :waveform_detected, []),
...> check(AudioPipelineChecks, :silence_threshold_exceeded, [])
...> ])
%Spek.AnyOf{
children: [
%Spek.Check{module: AudioPipelineChecks, fun: :waveform_detected, args: []},
%Spek.Check{module: AudioPipelineChecks, fun: :silence_threshold_exceeded, args: []}
]
}
"""
@doc type: :builder
@spec any_of([expression]) :: AnyOf.t()
def any_of(children) when is_list(children) do
%AnyOf{children: children}
end
@doc """
Builds an expression that requires at least one of two children to be true.
## Example
iex> any_of(
...> check(SubtitleChecks, :burn_in_detected, []),
...> check(SubtitleChecks, :timecode_aligned, [])
...> )
%Spek.AnyOf{
children: [
%Spek.Check{module: SubtitleChecks, fun: :burn_in_detected, args: []},
%Spek.Check{module: SubtitleChecks, fun: :timecode_aligned, args: []}
]
}
"""
@doc type: :builder
@spec any_of(expression, expression) :: AnyOf.t()
def any_of(a, b) do
%AnyOf{children: [a, b]}
end
@doc """
Builds a check.
## Example
iex> check(WeatherChecks, :temperature_below_freezing, [0])
%Spek.Check{module: WeatherChecks, fun: :temperature_below_freezing, args: [0]}
"""
@doc type: :builder
@spec check(module, fun, Check.args()) :: Check.t()
def check(module, fun, args \\ [:ctx]) do
%Check{module: module, fun: fun, args: args}
end
@doc """
Builds an expression that is always false.
## Example
iex> fail()
%Spek.Literal{result: false, satisfied?: false}
iex> fail(:error)
%Spek.Literal{result: :error, satisfied?: false}
iex> fail({:error, :insufficient_lighting})
%Spek.Literal{result: {:error, :insufficient_lighting}, satisfied?: false}
"""
@doc type: :builder
@spec fail(falsy) :: Literal.t()
def fail(result \\ false) do
%Literal{result: result, satisfied?: false}
end
@doc """
Builds an expression that always evaluates to the same value.
## Examples
iex> literal(true)
%Spek.Literal{result: true, satisfied?: true}
iex> literal(:ok)
%Spek.Literal{result: :ok, satisfied?: true}
iex> literal({:ok, "render_queue_ready"})
%Spek.Literal{result: {:ok, "render_queue_ready"}, satisfied?: true}
iex> literal(false)
%Spek.Literal{result: false, satisfied?: false}
iex> literal(:error)
%Spek.Literal{result: :error, satisfied?: false}
iex> literal({:error, :codec_not_supported})
%Spek.Literal{result: {:error, :codec_not_supported}, satisfied?: false}
"""
@doc type: :builder
@spec literal(result) :: Literal.t()
def literal(result) do
%Literal{result: result, satisfied?: to_boolean(result)}
end
@doc """
Builds an expression that evaluates to true unless both children are true.
## Example
iex> nand(check(RenderChecks, :gpu_available, []), check(RenderChecks, :texture_cache_warm, []))
%Spek.Not{
expression: %Spek.AllOf{
children: [
%Spek.Check{module: RenderChecks, fun: :gpu_available, args: []},
%Spek.Check{module: RenderChecks, fun: :texture_cache_warm, args: []}
]
}
}
"""
@doc type: :builder
@spec nand(expression, expression) :: expression
def nand(a, b) do
negate(all_of(a, b))
end
@doc """
Negates the given expression.
## Examples
iex> negate(literal(true))
%Spek.Not{expression: %Spek.Literal{result: true, satisfied?: true}}
iex> negate(check(EncodingChecks, :keyframe_aligned, []))
%Spek.Not{
expression: %Spek.Check{module: EncodingChecks, fun: :keyframe_aligned, args: []}
}
"""
@doc type: :builder
@spec negate(expression) :: Not.t()
def negate(expression) do
%Not{expression: expression}
end
@doc """
Builds an expression that requires all of its children to be false.
## Example
iex> none([check(AudioChecks, :noise_floor_exceeded, []), check(AudioChecks, :clipping_detected, [])])
%Spek.Not{
expression: %Spek.AnyOf{
children: [
%Spek.Check{module: AudioChecks, fun: :noise_floor_exceeded, args: []},
%Spek.Check{module: AudioChecks, fun: :clipping_detected, args: []}
]
}
}
"""
@doc type: :builder
@spec none([expression]) :: expression
def none(children) when is_list(children) do
negate(any_of(children))
end
@doc """
Builds an expression that evaluates to true if both children are false.
## Example
iex> nor(check(VideoChecks, :frame_dropped, []), check(VideoChecks, :desync_detected, []))
%Spek.Not{
expression: %Spek.AnyOf{
children: [
%Spek.Check{module: VideoChecks, fun: :frame_dropped, args: []},
%Spek.Check{module: VideoChecks, fun: :desync_detected, args: []}
]
}
}
"""
@doc type: :builder
@spec nor(expression, expression) :: expression
def nor(a, b) do
negate(any_of(a, b))
end
@doc """
Builds an expression that is always true.
## Example
iex> pass()
%Spek.Literal{result: true, satisfied?: true}
iex> pass(:ok)
%Spek.Literal{result: :ok, satisfied?: true}
iex> pass({:ok, "proxy_stream_ready"})
%Spek.Literal{result: {:ok, "proxy_stream_ready"}, satisfied?: true}
"""
@doc type: :builder
@spec pass(truthy) :: Literal.t()
def pass(result \\ true) do
%Literal{result: result, satisfied?: true}
end
@doc """
Builds the exclusive or of the given expressions.
## Example
iex> xor(check(PipelineChecks, :transcode_complete, []), check(PipelineChecks, :thumbnail_generated, []))
%Spek.AnyOf{
children: [
%Spek.AllOf{
children: [
%Spek.Check{module: PipelineChecks, fun: :transcode_complete, args: []},
%Spek.Not{
expression: %Spek.Check{
module: PipelineChecks,
fun: :thumbnail_generated,
args: []
}
}
]
},
%Spek.AllOf{
children: [
%Spek.Not{
expression: %Spek.Check{
module: PipelineChecks,
fun: :transcode_complete,
args: []
}
},
%Spek.Check{module: PipelineChecks, fun: :thumbnail_generated, args: []}
]
}
]
}
"""
@doc type: :builder
@spec xor(expression, expression) :: expression
def xor(a, b) do
any_of([
all_of(a, negate(b)),
all_of(negate(a), b)
])
end
## Evaluation
@doc """
Evaluates the given expression and returns the result as a boolean.
Stops early as soon as the final outcome is determined.
## Examples
iex> eval?(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "scene_042_render_complete"
...> )
true
iex> eval?(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
false
"""
@doc type: :evaluation
@spec eval?(expression, context) :: boolean
def eval?(expr, context \\ [])
def eval?(%Literal{satisfied?: satisfied?}, _) do
satisfied?
end
def eval?(
%Check{module: module, fun: fun, args: args},
context
) do
module
|> apply(fun, replace_args(args, context))
|> Spek.to_boolean()
end
def eval?(%Not{expression: expression}, context) do
not eval?(expression, context)
end
def eval?(%AllOf{children: children}, context) do
Enum.all?(children, &eval?(&1, context))
end
def eval?(%AnyOf{children: children}, context) do
Enum.any?(children, &eval?(&1, context))
end
@doc """
Evaluates the given expression and returns `:ok` or an error tuple.
Stops early as soon as the final outcome is determined.
## Examples
iex> eval(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "scene_042_render_complete"
...> )
:ok
iex> eval(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
{:error, %Spek.EvaluationError{message: "rule evaluation failed"}}
"""
@doc type: :evaluation
@spec eval(expression, context) :: :ok | {:error, EvaluationError.t()}
def eval(expression, context \\ []) do
if eval?(expression, context) do
:ok
else
{:error, EvaluationError.new()}
end
end
@doc """
Evaluates the given expression and raises an exception if it is not satisfied.
Stops early as soon as the final outcome is determined.
## Examples
iex> eval!(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "scene_042_render_complete"
...> )
:ok
iex> eval!(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
** (Spek.EvaluationError) rule evaluation failed
"""
@doc type: :evaluation
@spec eval!(expression, context) :: :ok | no_return()
def eval!(expression, context \\ []) do
if eval?(expression, context) do
:ok
else
raise EvaluationError
end
end
@doc """
Evaluates the given expression and returns the expression annotated with
evaluation results.
Stops early as soon as the final outcome is determined. The returned
expression only contains the evaluated parts.
## Examples
iex> eval_tree(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "scene_042_render_complete"
...> )
{
:ok,
%Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: true,
satisfied?: true
}
}
iex> eval_tree(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
{
:error,
%Spek.EvaluationError{
expression: %Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: false,
satisfied?: false
},
message: "rule evaluation failed"
}
}
"""
@doc type: :evaluation
@spec eval_tree(expression, context) ::
{:ok, expression} | {:error, EvaluationError.t()}
def eval_tree(expression, context \\ []) do
case do_eval_tree(expression, context, :halt) do
%{satisfied?: true} = evaluated_expression ->
{:ok, evaluated_expression}
%{satisfied?: false} = evaluated_expression ->
{:error, EvaluationError.with_expression(evaluated_expression)}
end
end
@doc """
Evaluates the given expression and returns the expression annotated with
evaluation results or raises an error.
Stops early as soon as the final outcome is determined. The returned
expression only contains the evaluated parts.
Raises an exception if the rule is not satisfied. Unlike `eval!/2`, the
exception contains the evaluated expression.
## Examples
iex> eval_tree!(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "scene_042_render_complete"
...> )
%Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: true,
satisfied?: true
}
iex> eval_tree!(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
** (Spek.EvaluationError) rule evaluation failed
"""
@doc type: :evaluation
@spec eval_tree!(expression, context) :: expression | no_return
def eval_tree!(expression, context \\ []) do
case do_eval_tree(expression, context, :halt) do
%{satisfied?: true} = evaluated_expression ->
evaluated_expression
%{satisfied?: false} = evaluated_expression ->
raise EvaluationError.with_expression(evaluated_expression)
end
end
@doc """
Evaluates the full given expression and returns the expression annotated with
the expression results.
Always evaluates the entire expression, even if the final outcome could be
determined earlier.
## Examples
iex> eval_tree_all(
...> all_of([
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> %Check{module: String, fun: :ends_with?, args: [:ctx, "_render_complete"]}
...> ]),
...> "scene_042_render_complete"
...> )
{
:ok,
%Spek.AllOf{
children: [
%Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: true,
satisfied?: true
},
%Spek.Check{
module: String,
fun: :ends_with?,
args: [:ctx, "_render_complete"],
result: true,
satisfied?: true
}
],
satisfied?: true
}
}
iex> eval_tree_all(
...> all_of([
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> %Check{module: String, fun: :ends_with?, args: [:ctx, "_render_complete"]}
...> ]),
...> "shot_042_render_complete"
...> )
{
:error,
%Spek.EvaluationError{
expression: %Spek.AllOf{
children: [
%Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: false,
satisfied?: false
},
%Spek.Check{
module: String,
fun: :ends_with?,
args: [:ctx, "_render_complete"],
result: true,
satisfied?: true
}
],
satisfied?: false
},
message: "rule evaluation failed"
}
}
"""
@doc type: :evaluation
@spec eval_tree_all(expression, context) ::
{:ok, expression} | {:error, EvaluationError.t()}
def eval_tree_all(expression, context \\ []) do
case do_eval_tree(expression, context, :cont) do
%{satisfied?: true} = evaluated_expression ->
{:ok, evaluated_expression}
%{satisfied?: false} = evaluated_expression ->
{:error, EvaluationError.with_expression(evaluated_expression)}
end
end
@doc """
Evaluates the full given expression and returns the expression annotated with
evaluation results or raises an error.
Raises if the expression is not satisfied. Unlike `eval!/2`, the raised
exception contains the evaluated expression.
Always evaluates the entire expression, even if the final outcome could be
determined earlier.
## Examples
iex> eval_tree_all!(
...> any_of([
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> %Check{module: String, fun: :ends_with?, args: [:ctx, "_render_complete"]}
...> ]),
...> "scene_042_render_complete"
...> )
%Spek.AnyOf{
satisfied?: true,
children: [
%Spek.Check{
module: String,
fun: :starts_with?,
args: [:ctx, "scene_"],
result: true,
satisfied?: true
},
%Spek.Check{
module: String,
fun: :ends_with?,
args: [:ctx, "_render_complete"],
result: true,
satisfied?: true
}
]
}
iex> eval_tree_all!(
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]},
...> "shot_042_render_complete"
...> )
** (Spek.EvaluationError) rule evaluation failed
"""
@doc type: :evaluation
@spec eval_tree_all!(expression, context) :: expression | no_return
def eval_tree_all!(expression, context \\ []) do
case do_eval_tree(expression, context, :cont) do
%{satisfied?: true} = evaluated_expression ->
evaluated_expression
%{satisfied?: false} = evaluated_expression ->
raise EvaluationError.with_expression(evaluated_expression)
end
end
defp do_eval_tree(%Literal{} = literal, _, _) do
literal
end
defp do_eval_tree(
%Check{module: module, fun: fun, args: args} = check,
context,
_
) do
result = apply(module, fun, replace_args(args, context))
%{check | result: result, satisfied?: Spek.to_boolean(result)}
end
defp do_eval_tree(
%Not{expression: expression} = not_expr,
context,
mode
) do
evaluated_expression =
do_eval_tree(expression, context, mode)
%{
not_expr
| expression: evaluated_expression,
satisfied?: not evaluated_expression.satisfied?
}
end
defp do_eval_tree(
%AllOf{children: children} = and_,
context,
mode
) do
{satisfied?, evaluated_children} =
Enum.reduce_while(
children,
{true, []},
&all_of_reducer(&1, &2, context, mode)
)
%{and_ | satisfied?: satisfied?, children: Enum.reverse(evaluated_children)}
end
defp do_eval_tree(
%AnyOf{children: children} = or_,
context,
mode
) do
{satisfied?, evaluated_children} =
Enum.reduce_while(
children,
{false, []},
&any_of_reducer(&1, &2, context, mode)
)
%{or_ | satisfied?: satisfied?, children: Enum.reverse(evaluated_children)}
end
defp all_of_reducer(expression, {previous_result, acc}, context, mode) do
case do_eval_tree(expression, context, mode) do
%{satisfied?: true} = expr ->
{:cont, {previous_result, [expr | acc]}}
%{satisfied?: false} = expr ->
{mode, {false, [expr | acc]}}
end
end
defp any_of_reducer(expression, {previous_result, acc}, context, mode) do
case do_eval_tree(expression, context, mode) do
%{satisfied?: true} = expr ->
{mode, {true, [expr | acc]}}
%{satisfied?: false} = expr ->
{:cont, {false or previous_result, [expr | acc]}}
end
end
defp replace_args([], _), do: []
defp replace_args(args, context) do
Enum.map(args, &replace_arg(&1, context))
end
defp replace_arg(:ctx, context), do: context
defp replace_arg({:ctx, key}, context)
when is_atom(key) and is_map(context) do
Map.fetch!(context, key)
end
defp replace_arg({:ctx, key}, context) when is_list(context) do
Keyword.fetch!(context, key)
end
defp replace_arg(arg, _), do: arg
@doc """
Evaluates the given expression with `eval_tree/2` and collects the results
into a list with `collect_results/2`.
In the success case, an `:ok` tuple with the list of success results is
returned.
In the error case, an `:error` tuple with a `Spek.EvaluationError` struct that
contains both the evaluation tree and the list of error results.
## Examples
iex> eval_collect(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01-12"
...> )
{:ok, [~D[2000-01-12]]}
iex> eval_collect(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01.12"
...> )
{
:error,
%Spek.EvaluationError{
expression: %Spek.Check{
module: Date,
fun: :from_iso8601,
args: [:ctx],
result: {:error, :invalid_format},
satisfied?: false
},
results: [:invalid_format],
message: "rule evaluation failed"
}
}
"""
@doc type: :evaluation
@spec eval_collect(expression, context) ::
{:ok, [term]} | {:error, EvaluationError.t()}
def eval_collect(expression, context \\ []) do
case eval_tree(expression, context) do
{:ok, expression} -> {:ok, collect_results(expression, :ok)}
{:error, error} -> {:error, EvaluationError.put_results(error)}
end
end
@doc """
Evaluates the given expression with `eval_tree/2` and collects the results
into a list with `collect_results/2`.
In the success case, the list of success results is returned.
In the error case, a `Spek.EvaluationError` exception is raised that
contains both the evaluation tree and the list of error results.
## Examples
iex> eval_collect!(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01-12"
...> )
[~D[2000-01-12]]
iex> eval_collect!(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01.12"
...> )
** (Spek.EvaluationError) rule evaluation failed
"""
@doc type: :evaluation
@spec eval_collect!(expression, context) :: [term] | no_return
def eval_collect!(expression, context \\ []) do
case eval_tree(expression, context) do
{:ok, expression} -> collect_results(expression, :ok)
{:error, error} -> raise EvaluationError.put_results(error)
end
end
@doc """
Evaluates the given expression with `eval_tree_all/2` and collects the results
into a list with `collect_results/2`.
In the success case, an `:ok` tuple with the list of success results is
returned.
In the error case, an `:error` tuple with a `Spek.EvaluationError` struct that
contains both the evaluation tree and the list of error results.
## Examples
iex> eval_collect_all(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01-12"
...> )
{:ok, [~D[2000-01-12]]}
iex> eval_collect_all(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01.12"
...> )
{
:error,
%Spek.EvaluationError{
expression: %Spek.Check{
module: Date,
fun: :from_iso8601,
args: [:ctx],
result: {:error, :invalid_format},
satisfied?: false
},
results: [:invalid_format],
message: "rule evaluation failed"
}
}
"""
@doc type: :evaluation
@spec eval_collect_all(expression, context) ::
{:ok, [term]} | {:error, EvaluationError.t()}
def eval_collect_all(expression, context \\ []) do
case eval_tree_all(expression, context) do
{:ok, expression} -> {:ok, collect_results(expression, :ok)}
{:error, error} -> {:error, EvaluationError.put_results(error)}
end
end
@doc """
Evaluates the given expression with `eval_tree_all/2` and collects the results
into a list with `collect_results/2`.
In the success case, the list of success results is returned.
In the error case, a `Spek.EvaluationError` exception is raised that
contains both the evaluation tree and the list of error results.
## Examples
iex> eval_collect_all!(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01-12"
...> )
[~D[2000-01-12]]
iex> eval_collect_all!(
...> %Check{module: Date, fun: :from_iso8601, args: [:ctx]},
...> "2000-01.12"
...> )
** (Spek.EvaluationError) rule evaluation failed
"""
@doc type: :evaluation
@spec eval_collect_all!(expression, context) :: [term] | no_return
def eval_collect_all!(expression, context \\ []) do
case eval_tree_all(expression, context) do
{:ok, expression} -> collect_results(expression, :ok)
{:error, error} -> raise EvaluationError.put_results(error)
end
end
## Filter/reject
@doc """
Filters the given enumerable to only retain the items that satisfy the given
expression.
## Example
iex> filter(
...> ["scene_042_render_complete", "shot_017_proxy_ready"],
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]}
...> )
["scene_042_render_complete"]
"""
@doc type: :evaluation
@spec filter(Enumerable.t(), expression) :: Enumerable.t()
def filter(items, expression) do
Enum.filter(items, &eval?(expression, &1))
end
@doc """
Filters the given enumerable to only retain the items that _do not_ satisfy
the given expression.
## Example
iex> reject(
...> ["scene_042_render_complete", "shot_017_proxy_ready"],
...> %Check{module: String, fun: :starts_with?, args: [:ctx, "scene_"]}
...> )
["shot_017_proxy_ready"]
"""
@doc type: :evaluation
@spec reject(Enumerable.t(), expression) :: Enumerable.t()
def reject(items, expression) do
Enum.reject(items, &eval?(expression, &1))
end
## Optimization
@doc """
Performs boolean algebra transformations on the given expression.
## Examples
iex> Spek.optimize(%AnyOf{
...> children: [
...> %AllOf{
...> children: [
...> %Check{module: RenderChecks, fun: :gpu_available, args: []},
...> %Check{module: RenderChecks, fun: :texture_cache_warm, args: []}
...> ]
...> },
...> %AllOf{
...> children: [
...> %Check{module: RenderChecks, fun: :color_space_valid, args: []},
...> %Check{module: RenderChecks, fun: :gpu_available, args: []}
...> ]
...> },
...> %Check{module: RenderChecks, fun: :fallback_renderer_enabled, args: []}
...> ]
...> })
%AnyOf{
children: [
%AllOf{
children: [
%Check{module: RenderChecks, fun: :gpu_available, args: []},
%AnyOf{
children: [
%Check{module: RenderChecks, fun: :texture_cache_warm, args: []},
%Check{module: RenderChecks, fun: :color_space_valid, args: []}
]
}
]
},
%Check{module: RenderChecks, fun: :fallback_renderer_enabled, args: []}
]
}
## Optimizations
| Optimization | Formula |
|---|---|
| Identity (AND) | `A and true = A` |
| Identity (OR) | `A or false = A` |
| Annihilation (AND) | `A and false = false` |
| Annihilation (OR) | `A or true = true` |
| Double negation elimination | `not (not A) = A` |
| Negation of literals | `not true = false`, `not false = true` |
| De Morgan’s law (AND) | `not (A and B) = (not A) or (not B)` |
| De Morgan’s law (OR) | `not (A or B) = (not A) and (not B)` |
| Empty conjunction | `allof() = true` |
| Empty disjunction | `anyof() = false` |
| Single-child conjunction elimination | `allof(A) = A` |
| Single-child disjunction elimination | `anyof(A) = A` |
| Deduplication (AND) | `A and A = A` |
| Deduplication (OR) | `A or A = A` |
| Factoring OR over AND | `(A and B) or (A and C) = A and (B or C)` |
| Factoring AND over OR | `(A or B) and (A or C) = A or (B and C)` |
| Absorption (OR) | `A or (A and B) = A` |
| Absorption (AND) | `A and (A or B) = A` |
"""
@doc type: :optimization
@spec optimize(expression) :: expression
def optimize(%Literal{} = literal) do
literal
end
def optimize(%Check{} = check) do
check
end
def optimize(%Not{expression: expression}) do
case optimize(expression) do
# not(not(expr)) == expr
%Not{expression: expr} ->
expr
# not(true) == false, not(false) == true
%Literal{satisfied?: bool} ->
%Literal{satisfied?: not bool, result: not bool}
# not (A and B) = (not A) or (not B)
%AllOf{children: children} ->
%AnyOf{children: Enum.map(children, &optimize(%Not{expression: &1}))}
# not (A or B) = (not A) and (not B)
%AnyOf{children: children} ->
%AllOf{children: Enum.map(children, &optimize(%Not{expression: &1}))}
# otherwise, not(expr)
expr ->
%Not{expression: expr}
end
end
def optimize(%AllOf{children: []}) do
%Literal{satisfied?: true, result: true}
end
def optimize(%AllOf{children: [child]}) do
optimize(child)
end
def optimize(%AllOf{children: [_ | _]} = all_of) do
case factorize(all_of) do
%AllOf{} = all_of ->
do_optimize_all_of(all_of)
%AnyOf{} = any_of ->
optimize(any_of)
end
end
def optimize(%AnyOf{children: []}) do
%Literal{satisfied?: false, result: false}
end
def optimize(%AnyOf{children: [child]}) do
optimize(child)
end
def optimize(%AnyOf{children: [_ | _]} = any_of) do
case factorize(any_of) do
%AnyOf{} = any_of ->
do_optimize_any_of(any_of)
%AllOf{} = all_of ->
optimize(all_of)
end
end
# credo:disable-for-next-line
defp do_optimize_all_of(%AllOf{children: [_ | _] = children}) do
{children, _} =
Enum.reduce_while(children, {[], MapSet.new()}, fn child, {acc, seen} ->
child = optimize(child)
cond do
# allof(A, false) = false
literal_false?(child) ->
{:halt, {false, nil}}
# allof(A, B, true) = allof(A, B)
literal_true?(child) ->
{:cont, {acc, seen}}
# allof(A, B, A) = allof(A, B) => skip duplicates
MapSet.member?(seen, child) ->
{:cont, {acc, seen}}
# If this is an AnyOf and we already have seen any of its children,
# remove it.
# A and (A or B) = A
any_of_child_seen?(child, seen) ->
{:cont, {acc, seen}}
# otherwise, add child to accumulator
true ->
# remove previously seen AnyOfs that have the current child among
# their children
# (A or B) and A = A
absorbed = reject_any_of_with_child(acc, child)
{:cont, {[child | absorbed], MapSet.put(seen, child)}}
end
end)
case children do
# wrap false from first condition in reducer
false -> %Literal{satisfied?: false, result: false}
# allof(A) = A
[child] -> child
# allof() = true
[] -> %Literal{satisfied?: true, result: true}
# return new allof
children -> %AllOf{children: Enum.reverse(children)}
end
end
# credo:disable-for-next-line
defp do_optimize_any_of(%AnyOf{children: children}) do
{children, _} =
Enum.reduce_while(
children,
{[], MapSet.new()},
fn child, {acc, seen} ->
child = optimize(child)
cond do
# anyof(A, true) = true
literal_true?(child) ->
{:halt, {true, nil}}
# anyof(A, B, false) = anyof(A, B)
literal_false?(child) ->
{:cont, {acc, seen}}
# anyOf(A, B, A) = anyof(A, B) => skip duplicates
MapSet.member?(seen, child) ->
{:cont, {acc, seen}}
# If this is an AllOf and we already have seen any of its children,
# remove it.
# A or (A and B) = A
all_of_child_seen?(child, seen) ->
{:cont, {acc, seen}}
# otherwise, add child to accumulator
true ->
# remove previously seen AllOfs that have the current child among
# their children
# (A and B) or A = A
absorbed = reject_all_of_with_child(acc, child)
{:cont, {[child | absorbed], MapSet.put(seen, child)}}
end
end
)
case children do
# wrap true from first condition in reducer
true -> %Literal{satisfied?: true, result: true}
# anyof(A) = A
[child] -> child
# anyof() = false
[] -> %Literal{satisfied?: false, result: false}
# return new anyof
children -> %AnyOf{children: Enum.reverse(children)}
end
end
defp literal_true?(%Literal{satisfied?: true}), do: true
defp literal_true?(_), do: false
defp literal_false?(%Literal{satisfied?: false}), do: true
defp literal_false?(_), do: false
defp reject_all_of_with_child(list, child) do
Enum.reject(list, fn
%AllOf{children: inner} -> child in inner
_ -> false
end)
end
defp reject_any_of_with_child(list, child) do
Enum.reject(list, fn
%AnyOf{children: inner} -> child in inner
_ -> false
end)
end
defp all_of_child_seen?(%AllOf{children: children}, seen) do
Enum.any?(seen, &(&1 in children))
end
defp all_of_child_seen?(_, _), do: false
defp any_of_child_seen?(%AnyOf{children: children}, seen) do
Enum.any?(seen, &(&1 in children))
end
defp any_of_child_seen?(_, _), do: false
defp factorize(%AllOf{children: children} = all_of) do
# find all AnyOf children; only factorize if there is more than one
{any_ofs, other} = Enum.split_with(children, &match?(%AnyOf{}, &1))
case any_ofs do
[] ->
all_of
[_] ->
all_of
_ ->
# find all children that are common among the AnyOfs
common_expressions = find_common_expressions(any_ofs)
if MapSet.size(common_expressions) == 0 do
all_of
else
# if there are common children, we can factorize
do_factorize_any_ofs(any_ofs, other, common_expressions)
end
end
end
defp factorize(%AnyOf{children: children} = any_of) do
# find all AllOf children; only factorize if there is more than one
{all_ofs, other} = Enum.split_with(children, &match?(%AllOf{}, &1))
case all_ofs do
[] ->
any_of
[_] ->
any_of
_ ->
# find all children that are common among the AllOfs
common_expressions = find_common_expressions(all_ofs)
if MapSet.size(common_expressions) == 0 do
any_of
else
# if there are common children, we can factorize
do_factorize_all_ofs(all_ofs, other, common_expressions)
end
end
end
defp find_common_expressions(ofs) do
ofs
|> Enum.map(fn
%AllOf{children: children} -> MapSet.new(children)
%AnyOf{children: children} -> MapSet.new(children)
end)
|> Enum.reduce(&MapSet.intersection/2)
end
defp do_factorize_all_ofs(all_ofs, other, common_expressions) do
common_expressions = MapSet.to_list(common_expressions)
# remove the common child expressions from all AllOfs
factored_branches =
Enum.map(all_ofs, fn %AllOf{children: children} ->
case children -- common_expressions do
# allof() = true
[] -> %Literal{satisfied?: true, result: true}
# allof(A) = A
[child] -> child
# if there is more than one child, build a new AllOf
children -> %AllOf{children: children}
end
end)
# (A and B) or (A and C) = A and (B or C)
new_all_of = %AllOf{
children: common_expressions ++ [%AnyOf{children: factored_branches}]
}
case other do
# if there were no none-AllOf expressions in the original AnyOf, just
# return the factorized AllOf expression
[] -> new_all_of
# if there were none-Allof expressions in the original AnyOf, wrap the
# factorized AllOf expression and the remaining expressions in an AnyOf
# (A and B) or (A and C) or D = (A and (B or C)) or D
_ -> %AnyOf{children: [new_all_of | other]}
end
end
defp do_factorize_any_ofs(any_ofs, other, common_expressions) do
common_expressions = MapSet.to_list(common_expressions)
# remove the common child expressions from all AnyOfs
factored_branches =
Enum.map(any_ofs, fn %AnyOf{children: children} ->
case children -- common_expressions do
# anyof() = false
[] -> %Literal{satisfied?: false, result: false}
# anyof(A) = A
[child] -> child
# if there is more than one child, build a new AnyOf
children -> %AnyOf{children: children}
end
end)
# (A or B) and (A or C) = A or (B and C)
new_any_of = %AnyOf{
children: common_expressions ++ [%AllOf{children: factored_branches}]
}
case other do
# if there were no none-AnyOf expressions in the original AllOf, just
# return the factorized AnyOf expression
[] -> new_any_of
# if there were none-AnyOf expressions in the original AllOf, wrap the
# factorized AnyOf expression and the remaining expressions in an AllOf
# (A or B) and (A or C) and D = (A or (B and C)) and D
_ -> %AllOf{children: [new_any_of | other]}
end
end
@doc """
Collects all tagged results from an expression into a list.
Results are returned without their `:ok` / `:error` tags.
## Examples
Literals and checks contribute only tagged tuple payloads. The plain result
values `:ok`, `:error`, `true` and `false` are not returned.
iex> Spek.collect_results(
...> %Literal{result: {:ok, "good"}, satisfied?: true}
...> )
["good"]
iex> Spek.collect_results(
...> %Literal{result: true, satisfied?: true}
...> )
[]
iex> Spek.collect_results(
...> %Check{
...> module: Checks,
...> fun: :some_check,
...> args: [],
...> result: {:error, "bad"},
...> satisfied?: false
...> }
...> )
["bad"]
The results of nested expressions are flattened.
iex> expression =
...> %AllOf{
...> children: [
...> %Literal{result: {:ok, "a"}, satisfied?: true},
...> %Literal{result: {:error, "b"}, satisfied?: false},
...> %Check{
...> module: Checks,
...> fun: :some_check,
...> args: [],
...> result: {:ok, "c"},
...> satisfied?: true
...> }
...> ]
...> }
iex> Spek.collect_results(expression)
["a", "b", "c"]
"""
@doc type: :evaluation
@spec collect_results(expression) :: [term]
def collect_results(expression) do
expression
|> do_collect_results()
|> List.flatten()
end
defp do_collect_results(%Check{result: {:ok, v}}), do: [v]
defp do_collect_results(%Check{result: {:error, v}}), do: [v]
defp do_collect_results(%Check{}), do: []
defp do_collect_results(%Literal{result: {:ok, v}}), do: [v]
defp do_collect_results(%Literal{result: {:error, v}}), do: [v]
defp do_collect_results(%Literal{}), do: []
defp do_collect_results(%Not{}), do: []
defp do_collect_results(%AllOf{children: children}) do
Enum.map(children, &do_collect_results/1)
end
defp do_collect_results(%AnyOf{children: children}) do
Enum.map(children, &do_collect_results/1)
end
@doc """
Collects the success or error results of an expression into a list.
## Examples
The returned list only contains results using `:ok` or `:error` tuples.
iex> Spek.collect_results(
...> %Literal{result: {:ok, "good"}, satisfied?: true},
...> :ok
...> )
["good"]
iex> Spek.collect_results(
...> %Check{
...> module: Checks,
...> fun: :some_check,
...> args: [],
...> result: {:error, "bad"},
...> satisfied?: false
...> },
...> :error
...> )
["bad"]
The plain result values `:ok`, `:error`, `true` and `false` are not returned.
iex> Spek.collect_results(
...> %Check{
...> module: Checks,
...> fun: :some_check,
...> args: [],
...> result: false,
...> satisfied?: false
...> },
...> :error
...> )
[]
The results of nested expressions are flattened.
iex> expression =
...> %AllOf{
...> children: [
...> %Literal{result: {:ok, "a"}, satisfied?: true},
...> %Literal{result: {:error, "b"}, satisfied?: false},
...> %Check{
...> module: Checks,
...> fun: :some_check,
...> args: [],
...> result: {:ok, "c"},
...> satisfied?: true
...> }
...> ]
...> }
iex> Spek.collect_results(expression, :ok)
["a", "c"]
iex> Spek.collect_results(expression, :error)
["b"]
`Not` reverses which tagged results are returned:
iex> expression =
...> %Not{
...> satisfied?: true,
...> expression: %Literal{
...> result: {:error, "bad"},
...> satisfied?: false
...> }
...> }
iex> Spek.collect_results(expression, :ok)
["bad"]
iex> Spek.collect_results(expression, :error)
[]
"""
@doc type: :evaluation
@spec collect_results(expression, :ok | :error) :: [term]
def collect_results(expression, only) when only in [:ok, :error] do
expression
|> do_collect_results(only == :ok)
|> List.flatten()
end
defp do_collect_results(%Check{result: {:ok, v}}, true), do: [v]
defp do_collect_results(%Check{result: {:error, v}}, false), do: [v]
defp do_collect_results(%Check{}, _), do: []
defp do_collect_results(%Literal{result: {:ok, v}}, true), do: [v]
defp do_collect_results(%Literal{result: {:error, v}}, false), do: [v]
defp do_collect_results(%Literal{}, _), do: []
defp do_collect_results(%Not{expression: expression}, only) do
do_collect_results(expression, not only)
end
defp do_collect_results(%AllOf{children: children}, only) do
Enum.map(children, &do_collect_results(&1, only))
end
defp do_collect_results(%AnyOf{children: children}, only) do
Enum.map(children, &do_collect_results(&1, only))
end
@doc false
def to_boolean(bool) when is_boolean(bool), do: bool
def to_boolean(:ok), do: true
def to_boolean({:ok, _}), do: true
def to_boolean(:error), do: false
def to_boolean({:error, _}), do: false
end