require "./src/wirewright"

require "./baz5_common"

module ::Ww::Backpath

class ::Ww::Backpath::Appender

# :nodoc:

def initialize(@preds : Term::Dict, @tip : Word::None | Word::Terminal | Word::Nonterminal)

end

# :nodoc:

EMPTY = Appender.new(preds: Term[], tip: Word::None.new)

# Constructs an empty backpath appender.

def self.new : Appender

EMPTY

end

private def push(tip1 : Word::Some) : Appender

Appender.new(backpath, tip1)

end

private def replace(tip1 : Word::Some) : Appender

Appender.new(@preds, tip1)

end

# The returned appender will update the key *term* of an existing entry. Its value

# is preserved. If the updated key collides with some existing key, the updated

# key's value wins.

def update_key(term) : Appender

case @tip

in Word::None, Word::Nonterminal

push Word::UpdateKey.new(Term.of(term))

in Word::Terminal

raise KeypathError.new

end

end

# The returned appender will update the value of an existing entry with the given *key*.

def update_value(key) : Appender

case @tip

in Word::None, Word::Nonterminal

push Word::UpdateValue.new(Term.of(key))

in Word::Terminal

raise KeypathError.new

end

end

# The returned appender will modify entries left after removing keys from *ee*. Each

# element of *ee* is converted to a Term using the block.

def delete_keys(ee : Enumerable(T), & : T -> Term) : Appender forall T

case @tip

in Word::None, Word::Nonterminal

keys = Term[].transaction do |commit|

ee.each { |object| commit << yield object }

end

push Word::Delete.new(keys)

in Word::Terminal

raise KeypathError.new

end

end

# Block-less variant of `delete_keys`.

def delete_keys(keys : Enumerable(Term)) : Appender

delete_keys(keys, &.itself)

end

# Block-less variant of `delete_keys`.

def delete_keys(keys : Term::Dict) : Appender

delete_keys(keys.items)

end

# Converts an `update` targeting one item into an update targeting a range of items.

# The size of the range is set by *size*. The returned appender is a **terminal** one:

# appending anything to it will fail.

def span(size, *, ord = 0u32) : Appender

case tip = @tip

when Word::UpdateValue

b = tip.key.to(Int32)

e = b + size

replace Word::Range.new(b, e, ord)

else

raise KeypathError.new

end

end

# Creates a pair with the given *key*. The returned appender is a **terminal** one:

# there is nothing to modify with it, since the value to be modified in fact does

# not exist.

def create_pair(key) : Appender

case @tip

in Word::None, Word::Nonterminal

push Word::CreateLeaf.new(Term.of(key))

in Word::Terminal

raise KeypathError.new

end

end

# Creates a pair with the given *key* and *value*. The returned appender will

# be modifying *value*.

def create_pair(key, *, value) : Appender

case @tip

in Word::None, Word::Nonterminal

push Word::Create.new(Term.of(key), Term.of(value), Term.of(value))

in Word::Terminal

raise KeypathError.new

end

end

# Converts an `update_value` of a single item into an insert of *value* before

# that item. The returned appender will be modifying *value*.

def insert_item(value, *, ord = 0) : Appender

case tip = @tip

when Word::UpdateValue

replace Word::Insert.new(tip.key.as_n, ord, Term.of(value))

else

raise KeypathError.new

end

end

# Shifts a numeric `update_value` *n* items forward.

def forward(n = 1) : Appender

case tip = @tip

when Word::UpdateValue

replace Word::UpdateValue.new(Term.of(tip.key + n))

else

raise KeypathError.new

end

end

# Shifts a numeric `update_value` *n* items backward.

def backward(n = 1) : Appender

forward(-n)

end

# Returns the backpath dict that this appender constructed so far.

def backpath : Term::Dict

case tip = @tip

in Word::None then @preds

in Word::Some then @preds.transaction &.concat(Word.terms(tip))

end

end

module ::Ww::Backpath::Word

extend self

alias Any = None | Some

alias Some = Atomic | Compound

# "Atomic" or "indivisible" words that actually exist in the trie.

alias Atomic = Create | CreateLeaf | Delete | Insert | Range | Pair

# "Compound words" are broken down into atomic words.

alias Compound = UpdateKey | UpdateValue

# Backpath words that do not have neighbors/successors in the trie (must stand at

# the end of a "sentence").

alias Terminal = CreateLeaf | Range

# Words that have neighbors/successors in the trie.

alias Nonterminal = Compound | Create | Delete | Insert

record UpdateKey, key : Term

record UpdateValue, key : Term

record None

record Create, key : Term, initial : Term, value : Term

record CreateLeaf, key : Term

record Insert, index : Term::Num, ord : UInt32, initial : Term

record Pair, key : Term

record Range, b : Int32, e : Int32, ord : UInt32

record Delete, keys : Term::Dict

record Key

record Value

# :nodoc:

SYM_PAIR = Term.of(:pair)

# :nodoc:

SYM_RESIDUE = Term.of(:residue)

# :nodoc:

SYM_RANGE = Term.of(:range)

# :nodoc:

SYM_CREATE_LEAF = Term.of(:"create-leaf")

# :nodoc:

SYM_CREATE = Term.of(:create)

# :nodoc:

SYM_INSERT = Term.of(:insert)

# Parses a subject term *subject* into an `Atomic` backpath word.

#

# Raises `KeypathError` if that cannot be done.

def atomic(subject : Term) : Atomic

raise KeypathError.new unless dict = subject.as_itemsonly_d?

raise KeypathError.new if dict.empty?

case {dict[0], dict.size - 1}

when {SYM_PAIR, 1}

_, key = dict

Pair.new(key)

when {SYM_RESIDUE, 1}

_, keys = dict

raise KeypathError.new unless keys = keys.as_d?

Delete.new(keys)

when {SYM_RANGE, 3}

_, b, e, ord = dict

raise KeypathError.new unless (b = b.as_n?) && (e = e.as_n?) && (ord = ord.as_n?)

Range.new(b.to(Int32), e.to(Int32), ord.to(UInt32))

when {SYM_CREATE_LEAF, 1}

_, key = dict

CreateLeaf.new(key)

when {SYM_CREATE, 2}

_, key, initial = dict

Create.new(key, initial, value: initial)

when {SYM_INSERT, 3}

_, index, ord, initial = dict

raise KeypathError.new unless (index = index.as_n?) && (ord = ord.as_n?)

Insert.new(index, ord.to(UInt32), initial)

else

raise KeypathError.new

end

end

# Yields substructure of *word* and/or *matchee* for the block to check out.

def checkout(word : Create, matchee : Term, &) : Nil

yield word.value

end

# :ditto:

def checkout(word : CreateLeaf, matchee : Term, &) : Nil

end

# :ditto:

def checkout(word : Insert, matchee : Term, &) : Nil

yield word.initial

end

# :ditto:

def checkout(word : Range, matchee : Term, &) : Nil

end

# :ditto:

def checkout(word : Delete, matchee : Term, &) : Nil

yield Term.exclude(matchee, word.keys.items)

end

def terms(word : Create) : Enumerable(Term)

{Term.of(:create, word.key, word.value)}

end

def terms(word : CreateLeaf) : Enumerable(Term)

{Term.of(:"create-leaf", word.key)}

end

def terms(word : Insert) : Enumerable(Term)

{Term.of(:insert, word.index, word.ord, word.initial)}

end

def terms(word : UpdateKey) : Enumerable(Term)

{Term.of(:pair, word.key), Term.of(:key)}

end

def terms(word : UpdateValue) : Enumerable(Term)

{Term.of(:pair, word.key), Term.of(:value)}

end

def terms(word : Range) : Enumerable(Term)

{Term.of(:range, word.b, word.e, word.ord)}

end

def terms(word : Delete) : Enumerable(Term)

{Term.of(:residue, word.keys)}

end

class ::Ww::KeypathError < Exception

alias Rewriter = RewriterContext, Rewrite::Any -> Rewrite::Any

alias Observer = Backpath::Appender, String, Rewrite::Some ->

alias Tick = ->

record RewriterContext, rng : Random, backpath : Backpath::Appender?, envs = Term[], observer : Observer | Tick = (Tick.new { }), options = Term[] do

def backpath(& : Backpath::Appender -> Backpath::Appender)

return self unless kp0 = @backpath

copy_with(backpath: yield kp0)

end

# Passthrough that notifies the observer (if any) of a *leaf rewrite*: rewrite that

# does not have a successor.

#

# "The observer" here means some kind of function that reacts to rewrites at backpaths.

# See `observer`.

def observable(leaf : Rewrite::Any, &explanation : -> String) : Rewrite::Any

if leaf.is_a?(Rewrite::Some)

case observer = @observer

in Observer

@backpath.try { |backpath| observer.call(backpath, yield, leaf) }

in Tick

observer.call

end

end

leaf

end

def noR : Rewriter

Rewriter.new { Rewrite.none }

def oneR(term term1 : Term) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce do |term0|

# Since this is a Rewrite introduction point we must fortify it with

# a diff(). Otherwise we risk rewriters to short-circuit if they cannot

# determine when to stop due to a sneaky One(T) -> Many([T]) or something

# like that.

ctx.observable(Rewrite.one(term1).diff(term0)) { "unconditional replace with one" }

end

end

def manyR(list : Term::Dict) : Rewriter

Rewriter.new do |ctx, staging|

# Just as above, we're defensive here.

staging.reduce do |term0|

ctx.observable(Rewrite.many(list).diff(term0)) { "unconditional replace with many" }

end

end

def envR(ctx, prefix, term term0)

ctx.envs.items.reverse_each do |env|

next unless pterm = env.follow?(prefix)

next unless pdict = pterm.as_d?

next unless term1 = pdict[term0]?

return ctx.observable(Rewrite.one(term1).diff(term0)) { "replace with value from the environment" }

end

Rewrite.none

def envR(prefix : Enumerable(Term)) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| envR(ctx, prefix, term) }

end

def envR(*prefix : Term) : Rewriter

envR(prefix)

EMPTY_PREFIX = [] of Term

def envR : Rewriter

envR(EMPTY_PREFIX)

private def splice(dict : Term::Dict, splices : Array({Term::Num, Term::Dict}))

splices.each do |start, splice|

next unless index = start.index32?

dict = dict.replace(index, Term.rep(splice.items))

end

dict

def itemsR(ctx0, term, successor, start : Int32) : Rewrite::Any

unless dict0 = term.as_d?

return Rewrite.none

end

# Fast path

if dict0.pairsonly?

return Rewrite.none

end

splices = nil

dict1 = dict0.transaction do |commit|

# We **must** call successor in proper order due to observers which are only

# capable of doing one backpath-insert at a time.

(start...dict0.itemsize).reverse_each do |index|

item = dict0[index]

ctx1 = ctx0.backpath &.update_value(index)

case rewrite = successor.call(ctx1, Rewrite.one(item))

in Rewrite::None

in Rewrite::One

commit.with(index, rewrite.term)

in Rewrite::Many

splices ||= [] of {Term::Num, Term::Dict}

splices << {Term[index], rewrite.list}

end

end

end

unless splices

# Dict transactions only modify the underlying dict upon the first with()/

# without()/etc. call. Since we only call with() on a Rewrite.one of the successor,

# and since we trust the successor in that its Rewrite.one signals change unconditionally,

# we thus consider a `same?` check sufficient to determine whether the dictionary

# was modified.

return dict0.same?(dict1) ? Rewrite.none : Rewrite.one(dict1)

end

dict1 = splice(dict1, splices)

Rewrite.one(dict1)

def itemsR(successor : Rewriter, *, start : Int32 = 0) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| itemsR(ctx, term, successor, start) }

end

def pairsR(ctx0, term, successor) : Rewrite::Any

unless dict0 = term.as_d?

return Rewrite.none

end

dict1 = dict0.transaction do |commit|

dict0.pairspart.each_entry do |key, value0|

ctx1 = ctx0.backpath &.update_value(key)

case rewrite = successor.call(ctx1, Rewrite.one(value0))

in Rewrite::None

in Rewrite::One then commit.with(key, rewrite.term)

in Rewrite::Many then commit.with(key, rewrite.list)

end

end

end

# See `itemsR` to learn why `same?` is sufficient here.

dict0.same?(dict1) ? Rewrite.none : Rewrite.one(dict1)

def pairsR(successor : Rewriter) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| pairsR(ctx, term, successor) }

end

def callR(ctx, term, callable)

# We do not trust *callable*, and perform an explicit diff to make sure the

# Rewrite *callable* returns reflects whether or not there actually was

# a rewrite.

rewrite = callable.call(term).diff(term)

ctx.observable(rewrite) { "rewrite" }

def callR(callable) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| callR(ctx, term, callable) }

end

def callR(&callable : Term -> Rewrite::Any) : Rewriter

callR(callable)

def chainR(ctx : RewriterContext, term : Term, a : Rewriter, b : Rewriter)

lhs = a.call(ctx, Rewrite.one(term))

rhs = b.call(ctx, lhs.as?(Rewrite::Some) || Rewrite.one(term))

{lhs, rhs}.rightmost?(Rewrite::Some) || Rewrite.none

def chainR(a : Rewriter, b : Rewriter) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| chainR(ctx, term, a, b) }

end

def chainR(a : Rewriter, b : Rewriter, *cs : Rewriter) : Rewriter

chainR(chainR(a, b), *cs)

def allR(ctx : RewriterContext, term : Term, a : Rewriter, b : Rewriter)

unless lhs = a.call(ctx, Rewrite.one(term)).as?(Rewrite::Some)

return Rewrite.none

end

b.call(ctx, lhs)

def allR(a : Rewriter, b : Rewriter) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| allR(ctx, term, a, b) }

end

def allR(a : Rewriter, b : Rewriter, *cs : Rewriter) : Rewriter

allR(allR(a, b), *cs)

def choiceR(ctx : RewriterContext, term : Term, a : Rewriter, b : Rewriter)

lhs = a.call(ctx, Rewrite.one(term))

lhs.as?(Rewrite::Some) || b.call(ctx, Rewrite.one(term))

def choiceR(a : Rewriter, b : Rewriter) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| choiceR(ctx, term, a, b) }

end

def choiceR(a : Rewriter, b : Rewriter, *cs) : Rewriter

choiceR(choiceR(a, b), *cs)

def choiceR(a : Rewriter) : Rewriter

a

def entriesR(successor : Rewriter) : Rewriter

chainR(itemsR(successor), pairsR(successor))

def entryR1(ctx0, dict, key, value, successor)

ctx1 = ctx0.backpath &.update_value(key)

case rewrite = successor.call(ctx1, Rewrite.one(value))

in Rewrite::None

Rewrite.none

in Rewrite::One

Rewrite.one(dict.with(key, rewrite.term))

in Rewrite::Many

if index = dict.index32?(key)

Rewrite.one(dict.replace(index, Term.rep(rewrite.list.items)))

else

Rewrite.one(dict.with(key, rewrite.list))

end

end

def entryR(ctx, term, successor)

unless dict = term.as_d?

return Rewrite.none

end

case dict.size

when 0 # Empty dict, nothing to randomize

Rewrite.none

when 1 # One entry, nothing to randomize

key, value = dict.nth(0)

entryR1(ctx, dict, key, value, successor)

when 2 # Two elements, randomize A,B s. B,A

indices = { {0, 1}, {1, 0} }[(0..1).sample(ctx.rng)]

indices.each do |index|

key, value = dict.nth(index)

case rewrite = entryR1(ctx, dict, key, value, successor)

in Rewrite::None

in Rewrite::Some then return rewrite

end

end

# No rewritable entries

Rewrite.none

else # More than two elements, visit in disorder

n = dict.size.to_u32

state, prime = Disorder.state(n, ctx.rng)

n.times do

state = index = Disorder.next(n, state, prime)

key, value = dict.nth(index.to_i)

case rewrite = entryR1(ctx, dict, key, value, successor)

in Rewrite::None

in Rewrite::Some then return rewrite

end

end

# No rewritable entries

Rewrite.none

end

def entryR(successor : Rewriter) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| entryR(ctx, term, successor) }

end

{% for row in { {:item, :pair}, {:pair, :item} } %}

{% lpart, rpart = row %}

# Rewrites one random {{lpart.id}} of a dictionary using *successor*.

def {{lpart.id}}R(successor : Rewriter) : Rewriter

slave = entryR(successor)

Rewriter.new do |ctx, staging|

staging.reduce do |term|

unless dict = term.as_d?

next Rewrite.none

end

case rewrite = slave.call(ctx, Rewrite.one(dict.{{lpart.id}}spart))

in Rewrite::None

Rewrite.none

in Rewrite::One

# entryR always returns a dictionary, but we're a little too loose

# on the types so we have to error-cast. Whatever.

Rewrite.one(rewrite.term.as_d | dict.{{rpart.id}}spart)

in Rewrite::Many

raise "BUG: entryR returned Rewrite::Many"

end

end

end

end

{% end %}

def recR : {(Rewriter -> Rewriter), Rewriter}

slot = nil

set = ->(rewriter : Rewriter) { slot = rewriter }

rec = Rewriter.new do |ctx, staging|

next Rewrite.none unless slot_ = slot

slot_.call(ctx, staging)

end

{set, rec}

def selR(ctx, term, selector, successor)

if env = M1::Operator.match?(Term[], selector, term)

if rewritee = env[:rewritee]?

return successor.call(ctx, Rewrite.one(rewritee)).as?(Rewrite::Some) || Rewrite.one(rewritee)

end

end

Rewrite.none

def selR(selector, successor)

Rewriter.new do |ctx, staging|

staging.reduce { |term| selR(ctx, term, selector, successor) }

end

def rejR(ctx, term, selector, successor)

if M1.probe?(Term[], selector, term)

return Rewrite.none

end

successor.call(ctx, Rewrite.one(term))

def rejR(selector, successor)

Rewriter.new do |ctx, staging|

staging.reduce { |term| rejR(ctx, term, selector, successor) }

end

def selR(selector : Term, successor : Rewriter) : Rewriter

selR(M1.operator(selector), successor)

def rejR(selector : Term, successor : Rewriter) : Rewriter

rejR(M1.operator(selector), successor)

SELR_SELECTOR_CACHE = SyncLRU(String, Term).new(1024, by_ref: true)

def selR(selector : String, successor : Rewriter) : Rewriter

selR(SELR_SELECTOR_CACHE.put_if_absent(selector) { ML.term(selector) }, successor)

def rejR(selector : String, successor : Rewriter) : Rewriter

rejR(SELR_SELECTOR_CACHE.put_if_absent(selector) { ML.term(selector) }, successor)

def switchR(branches : Enumerable({String, Rewriter}) | Enumerable({Term, Rewriter}) | Enumerable({M1::Operator::Any, Rewriter})) : Rewriter

choice = nil

branches.each do |selector, successor|

rewriter = selR(selector, successor)

choice = choice ? choiceR(choice, rewriter) : rewriter

end

choice || noR

def switchR(*branches : {String, Rewriter} | {Term, Rewriter} | {M1::Operator::Any, Rewriter})

switchR(branches)

def dfsR(successor : Rewriter) : Rewriter

set, rec = recR

set.call choiceR(successor, entriesR(rec))

def itemdfsR(successor : Rewriter) : Rewriter

set, rec = recR

set.call choiceR(successor, itemsR(rec))

def exhR(ctx, term, successor, limit)

state = Rewrite.one(term)

changed = false

(0...limit).each do

case rewrite = successor.call(ctx, state)

in Rewrite::Some

state = rewrite

changed = true

in Rewrite::None

break

end

end

changed ? state : Rewrite.none

def absR(successor) : Rewriter

set, rec = recR

set.call choiceR(successor, entryR(rec))

def exhR(successor : Rewriter, *, limit = nil) : Rewriter

Rewriter.new do |ctx, staging|

staging.reduce { |term| exhR(ctx, term, successor, limit) }

end

module Relr

record Ready, rewrite : Rewrite::Any

record Ascend, ascent : Int32

record None

# Just like in `itemsR`, here we must iterate in a keypath-friendly

# way so that observers that rely solely on {keypath, rewrite} pairs can

# reconstruct what we're doing here without messing up indices etc.

private def self.each_entry_keypath_friendly(dict : Term::Dict, &)

(0...dict.itemsize).reverse_each do |index|

yield Term.of(index), dict[index]

end

dict.pairspart.each_entry do |key, value|

yield key, value

end

end

def self.relr(ctx0, bottom, term, ascent, env, successor)

if M1::Operator.probe?(env, bottom, term)

return Ascend.new(ascent)

end

unless dict0 = term.as_d?

return None.new

end

splices = nil

dict1 = dict0.transaction do |commit|

each_entry_keypath_friendly(dict0) do |key, value|

ctx1 = ctx0.backpath &.update_value(key)

case response = relr(ctx1, bottom, value, ascent, env, successor)

in None

next

in Ascend

unless response.ascent.zero?

return response.copy_with(ascent: response.ascent - 1)

end

rewrite = successor.call(ctx1, Rewrite.one(value))

in Ready

rewrite = response.rewrite

end

case rewrite

in Rewrite::None

in Rewrite::One

commit.with(key, rewrite.term)

in Rewrite::Many

if index = dict0.index?(key)

splices ||= [] of {Term::Num, Term::Dict}

splices << {index, rewrite.list}

else

commit.with(key, rewrite.list)

end

end

end

end

unless splices

# See `itemsR` to learn why this `same?` check is sufficient here.

return Ready.new(dict0.same?(dict1) ? Rewrite.none : Rewrite.one(dict1))

end

dict1 = splice(dict0, splices)

Ready.new(Rewrite.one(dict1))

end

module RelrEnv

extend self

alias Any = Literal | Option

record Literal, dict : Term::Dict

record Option, key : Term

def resolve(ctx, env : Literal) : Term::Dict

env.dict

end

def resolve(ctx, env : Option) : Term::Dict

return Term[] unless candidate = ctx.options[env.key]?

return Term[] unless dict = candidate.as_d?

dict

end

def relR(bottom : M1::Operator::Any, successor : Rewriter, *, ascent : Int32 = 0, env : RelrEnv::Any = RelrEnv::Literal.new(Term[])) : Rewriter

if ascent.negative?

raise ArgumentError.new("ascent must be positive or 0")

end