Packages
fixpoint
0.1.0
0.22.2
0.22.1
0.21.5
0.21.4
0.21.3
0.21.2
0.21.1
0.21.0
0.20.6
0.20.5
0.20.4
0.20.3
0.20.2
0.20.1
0.19.5
0.19.4
0.19.3
0.19.2
0.19.1
0.18.2
0.18.1
0.17.6
0.17.5
0.17.4
0.17.3
0.17.2
0.17.1
0.16.5
0.16.4
0.16.3
0.16.2
0.16.1
0.16.0
0.15.6
0.15.5
0.15.4
0.15.3
0.15.2
0.15.1
0.15.0
0.14.9
0.14.8
0.14.7
0.14.6
0.14.5
0.14.4
0.14.3
0.14.2
0.14.1
0.13.5
0.13.4
0.13.2
0.13.1
0.12.9
0.12.8
0.12.7
0.12.6
0.12.5
0.12.4
0.12.2
0.12.1
0.11.8
0.11.7
0.11.6
0.11.5
0.11.4
0.11.3
0.11.2
0.11.1
0.10.7
0.10.6
0.10.5
0.10.4
0.10.3
0.10.2
0.10.1
0.9.12
0.9.11
0.9.10
0.9.9
0.9.8
0.9.7
0.9.6
0.9.5
0.9.4
0.9.3
0.9.2
0.9.1
0.9.0
0.8.52
0.8.51
0.8.50
0.8.49
0.8.48
0.8.46
0.8.44
0.8.43
0.8.42
0.8.41
0.8.40
0.8.39
0.8.38
0.8.37
0.8.36
0.8.35
0.8.34
0.8.33
0.8.32
0.8.31
0.8.30
0.8.29
0.8.28
0.8.27
0.8.26
0.8.25
0.8.24
0.8.23
0.8.22
0.8.21
0.8.20
0.8.19
0.8.18
0.8.17
0.8.16
0.8.15
0.8.14
0.8.13
0.8.12
0.8.11
0.8.10
0.8.9
0.8.8
0.8.7
0.8.6
0.8.5
0.8.4
0.8.3
0.8.2
0.8.1
0.8.0
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.12
0.5.11
0.5.10
0.5.9
0.5.8
0.5.7
0.5.6
0.5.5
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.3
0.4.2
0.4.1
0.4.0
0.3.6
0.3.5
0.3.4
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.1.3
0.1.2
0.1.1
0.1.0
Constraint Programming Solver
Current section
Files
Jump to
Current section
Files
lib/solver/propagation/propagator.ex
defmodule CPSolver.Propagator do
alias CPSolver.Variable
alias CPSolver.Common
alias CPSolver.Utils
require Logger
@callback filter(variables :: list()) :: map() | :stable | :failure
@callback variables(args :: list()) :: list()
@domain_changes Common.domain_changes()
defmacro __using__(_) do
quote do
@behaviour CPSolver.Propagator
def variables(args) do
args
end
defoverridable variables: 1
end
end
@behaviour GenServer
## Create a propagator thread; 'propagator' is a tuple {propagator_mod, args} where propagator_mod
## is an implementation of CPSolver.Propagator
##
## Propagator thread is a process that handles life cycle of a propagator.
## TODO: details to follow.
def create_thread(space, propagator, opts \\ [id: make_ref()])
def create_thread(
space,
{propagator_mod, propagator_args} = _propagator,
opts
)
when is_atom(propagator_mod) do
{:ok, _thread} =
GenServer.start(__MODULE__, [space, propagator_mod, propagator_args, opts])
end
def create_thread(space, propagator, opts) do
[propagator_mod | args] = Tuple.to_list(propagator)
create_thread(space, {propagator_mod, args}, opts)
end
def dispose(%{thread: pid} = _thread) do
(Process.alive?(pid) && GenServer.stop(pid)) || :not_found
end
## Subscribe propagator thread to variables' events
defp subscribe_to_variables(thread, variables) do
Enum.each(variables, fn var -> subscribe_to_var(thread, var) end)
end
defp subscribe_to_var(thread, variable) do
Utils.subscribe(thread, {:variable, variable.id})
end
defp unsubscribe_from_var(thread, var_id) do
Utils.unsubscribe(thread, {:variable, var_id})
end
## GenServer callbacks
@impl true
def init([space, propagator_mod, args, opts]) do
bound_vars = Variable.bind_variables(space, propagator_mod.variables(args))
subscribe_to_variables(self(), bound_vars)
propagator_id = Keyword.get(opts, :id, make_ref())
Utils.subscribe(space, {:propagator, propagator_id})
{:ok,
%{
id: propagator_id,
space: space,
propagator_impl: propagator_mod,
args: args,
unfixed_variables:
Enum.reduce(bound_vars, Map.new(), fn var, acc ->
(Variable.fixed?(var) && acc) || Map.put(acc, var.id, %{active: true})
end),
propagator_opts: opts,
on_startup: true
}, {:continue, :filter}}
end
@impl true
def handle_continue(:filter, data) do
filter(data)
{:noreply, data}
end
@impl true
def handle_info({:fail, var}, data) do
Logger.debug("#{inspect(data.id)} Propagator: Failure for #{inspect(var)}")
publish(data, :failed)
{:stop, :normal, data}
end
def handle_info({:no_change, var}, data) do
Logger.debug("#{inspect(data.id)} Propagator: no change for #{inspect(var)}")
if data.on_startup && entailed?(data) do
Logger.debug("#{inspect(data.id)} Propagator is entailed (on a startup)")
publish(data, :entailed)
{:stop, :normal, data}
else
{:noreply,
data
|> Map.put(:on_startup, false)
|> update_active(var, false)
|> tap(fn new_data ->
if stable?(new_data) do
handle_stable(new_data)
end
end)}
end
end
def handle_info({:fixed, var}, data) do
new_data = update_unfixed(data, var)
if entailed?(new_data) do
Logger.debug("#{inspect(data.id)} Propagator is entailed (on filtering)")
publish(data, :entailed)
{:stop, :normal, new_data}
else
filter(new_data)
{:noreply, new_data}
end
end
def handle_info({domain_change, var}, data) when domain_change in @domain_changes do
Logger.debug("#{inspect(data.id)} Propagator: #{inspect(domain_change)} for #{inspect(var)}")
filter(data)
{:noreply, update_active(data, var, true)}
end
### end of GenServer callbacks
defp filter(%{propagator_impl: mod, args: args} = data) do
case mod.filter(args) do
:stable ->
handle_stable(data)
_res ->
handle_running(data)
end
end
defp handle_stable(data) do
Logger.debug("#{inspect(data.id)} Propagator #{inspect(self())} is stable")
publish(data, :stable)
end
defp handle_running(data) do
publish(data, :running)
end
defp entailed?(%{unfixed_variables: vars} = _data) do
entailed?(vars)
end
defp entailed?(vars) when is_map(vars) do
map_size(vars) == 0
end
defp update_unfixed(%{unfixed_variables: unfixed} = data, var) do
unsubscribe_from_var(self(), var)
%{data | unfixed_variables: Map.delete(unfixed, var)}
end
defp update_active(%{unfixed_variables: unfixed} = data, var, active?) do
%{
data
| unfixed_variables:
if Map.has_key?(unfixed, var) do
Map.update!(unfixed, var, fn content -> Map.put(content, :active, active?) end)
else
unfixed
end
}
end
defp stable?(%{unfixed_variables: unfixed} = _data) do
Enum.all?(unfixed, fn {_k, v} -> !v.active end)
end
defp publish(data, message) do
Utils.publish({:propagator, data.id}, {message, data.id})
end
end