###
# Modern Albufeira Prolog Interpreter
#
# Warranty & Liability
# To the extent permitted by applicable law and unless explicitly
# otherwise agreed upon, XLOG Technologies AG makes no warranties
# regarding the provided information. XLOG Technologies AG assumes
# no liability that any problems might be solved with the information
# provided by XLOG Technologies AG.
#
# Rights & License
# All industrial property rights regarding the information - copyright
# and patent rights in particular - are the sole property of XLOG
# Technologies AG. If the company was not the originator of some
# excerpts, XLOG Technologies AG has at least obtained the right to
# reproduce, change and translate the information.
#
# Reproduction is restricted to the whole unaltered document. Reproduction
# of the information is only allowed for non-commercial uses. Selling,
# giving away or letting of the execution of the library is prohibited.
# The library can be distributed as part of your applications and libraries
# for execution provided this comment remains unchanged.
#
# Restrictions
# Only to be distributed with programs that add significant and primary
# functionality to the library. Not to be distributed with additional
# software intended to replace any components of the library.
#
# Trademarks
# Jekejeke is a registered trademark of XLOG Technologies AG.
##

from collections import OrderedDict

MASK_PRED_PREHASH = 0x00000010
MASK_PRED_ARITH = 0x00000008
MASK_PRED_SPECIAL = 0x00000004
MASK_PRED_TEST = 0x00000002
MASK_PRED_DYNAMIC = 0x00000001

MASK_TOUCH_PREHASH = 0x00000004
MASK_TOUCH_BOTTOM = 0x00000002
MASK_TOUCH_DYNAMIC = 0x00000001
MASK_REMOVE_REVERSE = 0x00000001

VAR_MASK_SEEN = 0x40000000
VAR_MASK_EVEN = 0x20000000
VAR_MASK_ODD = 0x10000000
VAR_MASK_STATE = VAR_MASK_EVEN | VAR_MASK_ODD
VAR_MASK_BITS = 28
VAR_MASK_SERNO = (1 << VAR_MASK_BITS) - 1

kb = {}
stage = -1

MAX_INDEX = 2
ROPE_LOW = 24
ROPE_HIGH = 40

###
# Set the clause and predicate current stage.
#
# @param num The current stage.
##
def set_stage(num):
    global stage
    stage = num


###
# Set the clause current partition.
#
# @param str The current partition.
##
def set_partition(path):
    engine.partition = path


################################################################
# Engine                                                       #
################################################################

###
# Create a slow state engine.
#
# @constructor The engine.
##
class Engine:
    def __init__(self):
        self.signal = NotImplemented
        self.abort = lambda: None
        self.flags = 0
        self.text_output = NotImplemented
        self.text_error = NotImplemented
        self.text_input = NotImplemented
        self.low = 0
        self.high = 0
        self.serno = 0
        self.backtrail = None
        self.partition = "system" if stage == -1 else "user"


engine = Engine()


def set_engine(ptr):
    global engine
    engine = ptr


################################################################
# Variable & Compound                                          #
################################################################

###
# Create a Prolog variable.
#
# @constructor The new variable.
##
class Variable:
    def __init__(self):
        self.instantiated = NotImplemented
        self.flags = VAR_MASK_SERNO
        self.tail = None


###
# Check whether an object is a Prolog variable.
#
# @param obj The object.
# @return True if the object is a variable, otherwise false.
##
def is_variable(obj):
    return isinstance(obj, Variable)


###
# Compute a variable serno.
#
# @param alpha The variable.
# @return The serno.
##
def variable_serno(alpha):
    val = alpha.flags & VAR_MASK_SERNO
    if val == VAR_MASK_SERNO:
        if engine.low < engine.high:
            val = engine.low
            engine.low = val + 1
        else:
            val = engine.serno
            engine.serno = val + 1
        alpha.flags &= ~VAR_MASK_SERNO
        alpha.flags |= val
    return val


###
# Create an element.
#
# @param functor The functor.
# @param args The arguments.
# @constructor The new element.
##
class Element:
    def __init__(self, functor, args):
        self.functor = functor
        self.args = args


###
# Check whether an object is an element.
#
# @param obj The object.
# @return True if the object is an element, otherwise false.
##
def is_element(obj):
    return isinstance(obj, Element)


###
# Create a Prolog structure.
#
# @param functor The functor.
# @param args The arguments.
# @constructor The new Prolog structure.
##
class Structure(Element):
    def __init__(self, functor, args):
        super().__init__(functor, args)


###
# Check whether an object is a Prolog structure.
#
# @param obj The object.
# @return True if the object is a structure, otherwise false.
##
def is_structure(obj):
    return isinstance(obj, Structure)


###
# Create a Prolog compound.
#
# @param functor The functor.
# @param args The arguments.
# @constructor The new compound.
##
class Compound(Structure):
    def __init__(self, functor, args):
        super().__init__(functor, args)
        self.walk = 0


####
# Check whether an object is a Prolog compound.
#
# @param obj The object.
# @return True if the object is a compound, otherwise false.
##
def is_compound(obj):
    return isinstance(obj, Compound)


################################################################
# Slot & Functor                                               #
################################################################

###
# Create a Albufeira Code place.
##
class Place:
    def __init__(self, index):
        self.index = index


###
# Check whether an object is a place.
#
# @param obj The object.
# @return boolean True if the object is a place, otherwise false.
##
def is_place(obj):
    return isinstance(obj, Place)


###
# Create a Albufeira Code skeleton.
#
# @param functor The functor.
# @param args    The arguments.
##
class Skeleton(Element):
    def __init__(self, functor, args):
        super().__init__(functor, args)


###
# Check whether an object is a skeleton.
#
# @param obj The object.
# @return boolean True if the object is a skeleton, otherwise false.
##
def is_skeleton(obj):
    return isinstance(obj, Skeleton)


################################################################
# deref() and copy_term()                                      #
################################################################

###
# Dereference a Prolog term.
#
# @param term The Prolog term.
# @return The derferenced Prolog term.
##
def deref(term):
    while is_variable(term) and term.instantiated is not NotImplemented:
        term = term.instantiated
    return term


###
# Copy a Prolog term. Can handle cyclic terms.
#
# @param first The Prolog term.
# @return The copy.
##
def copy_term(first):
    try:
        res = walk_copy(first)
    finally:
        walk_uncopy(first)
    return res


def walk_copy(first):
    stack = None
    while True:
        first = deref(first)
        if is_variable(first):
            if first.tail is None:
                peek = Variable()
                first.tail = peek
                first = peek
            else:
                first = first.tail
        elif is_compound(first):
            if not is_compound(first.functor):
                first.functor = Compound(first.functor,
                                         [NotImplemented] * len(first.args))
                first.walk &= ~VAR_MASK_SERNO
                stack = stack_push(stack, first)
                first = first.args[0]
                continue
            else:
                first = first.functor
        item = stack_peek(stack)
        while (item is not None and
               (item.walk & VAR_MASK_SERNO) == len(item.args) - 1):
            item.functor.args[item.walk & VAR_MASK_SERNO] = first
            first = item.functor
            stack_pop(stack)
            item = stack_peek(stack)
        if item is None:
            return first
        else:
            item.functor.args[item.walk & VAR_MASK_SERNO] = first
            item.walk += 1
            first = item.args[item.walk & VAR_MASK_SERNO]


def walk_uncopy(first):
    stack = None
    while True:
        first = deref(first)
        if is_variable(first):
            if first.tail is not None:
                first.tail = None
        elif is_compound(first):
            if is_compound(first.functor):
                first.functor = first.functor.functor
                if 0 != len(first.args) - 1:
                    first.walk &= ~VAR_MASK_SERNO
                    stack = stack_push(stack, first)
                first = first.args[0]
                continue
        item = stack_peek(stack)
        if item is None:
            return
        else:
            item.walk += 1
            first = item.args[item.walk & VAR_MASK_SERNO]
            if (item.walk & VAR_MASK_SERNO) == len(item.args) - 1:
                stack_pop(stack)


################################################################
# Binary Work                                                  #
################################################################

###
# Create a binary work item.
#
# @param first The first Prolog term.
# @param second The second Prolog term.
# @param idx The index.
##
class Item:
    def __init__(self, first, second, idx):
        self.first = first
        self.second = second
        self.idx = idx


################################################################
# Stack Array                                                  #
################################################################

###
# The function returns the same stack extended by a work item.
#
# @param stack The stack.
# @param elem The work item.
# @return The new stack.
##
def stack_push(stack, elem):
    if stack is None:
        stack = []
    stack.append(elem)
    return stack


###
# The function returns the top work item or null.
#
# @param stack The stack.
# @return The work item.
##
def stack_peek(stack):
    if stack is None:
        return None
    if len(stack) == 0:
        return None
    return stack[len(stack)-1]


###
# The routine removes the top work item from the stack.
#
# @param stack The stack.
##
def stack_pop(stack):
    del stack[len(stack)-1]


################################################################
# Clauses Lifecycle                                            #
################################################################

class Goal:
    def __init__(self, size, body, cutvar):
        self.size = size
        self.body = body
        self.cutvar = cutvar


###
# Check whether the object is a goal.
#
# @param obj The object.
# @return True if the object is a goal, otherwise false.
##
def is_goal(obj):
    return isinstance(obj, Goal)


class Clause:
    def __init__(self, size, functor, head, body, cutvar):
        self.size = size
        self.functor = functor
        self.head = head
        self.body = body
        self.cutvar = cutvar
        self.creator = NotImplemented
        self.remover = NotImplemented
        self.shard = ""


###
# Check whether the object is a clause.
#
# @param obj The object.
# @return True if the object is a clause, otherwise false.
##
def is_clause(obj):
    return isinstance(obj, Clause)


###
# Create a logical.
#
# @param cache The cache of non-deleted clauses.
# @param count The counter of non-deleted clauses.
# @param data The clause list.
##
class Logical:
    def __init__(self, cache, count, data):
        self.cache = cache
        self.count = count
        self.data = data


###
# Check whether an object is a logical.
#
# @param obj The object.
# @return True if the object is a logical, otherwise false.
##
def is_logical(obj):
    return isinstance(obj, Logical)


###
# Create a stick.
#
# @param rope The rope.
# @param guards The variabe guards.
# @param maps The index map.
##
class Stick:
    def __init__(self, rope, guards, maps):
        self.rope = rope
        self.guards = guards
        self.maps = maps


###
# Check whether an object is a stick.
#
# @param obj The object.
# @return True if the object is a stick, otherwise false.
##
def is_stick(obj):
    return isinstance(obj, Stick)


def index_value(temp, body, flags):
    j = 0
    while True:
        if not is_place(temp):
            if (flags & MASK_PRED_PREHASH) != 0:
                if is_frozen(temp):
                    temp = temp.hash
                elif not is_skeleton(temp):
                    temp = object_hash_code(temp)
                else:
                    temp = NotImplemented
            else:
                if is_element(temp):
                    temp = temp.functor
            break
        if (temp is not NotImplemented and
                (flags & MASK_PRED_DYNAMIC) == 0 and
                j < len(body)):
            peek = body[j]
            j += 1
            if (is_element(peek) and
                    "=" == site_name(peek.functor) and
                    len(peek.args) == 2):
                if temp is peek.args[0]:
                    temp = peek.args[1]
                elif temp is peek.args[1]:
                    temp = peek.args[0]
                continue
            elif (is_element(peek) and
                  "nonvar" == site_name(peek.functor) and
                  len(peek.args) == 1):
                continue
        temp = NotImplemented
        break
    return temp


def site_name(obj):
    if is_cache(obj):
        return obj.name
    else:
        return obj


################################################################
# Knowledgebase                                                #
################################################################

###
# Create a provable.
#
# @constructor The new provable.
##
class Provable:
    def __init__(self):
        self.flags = 0
        self.func = NotImplemented
        self.creator = stage
        self.remover = NotImplemented
        self.overlay = NotImplemented


###
# Check whether an object is a provable.
#
# @param obj The object.
# @return True if the object is a provable, otherwise false.
##
def is_provable(obj):
    return isinstance(obj, Provable)


###
# Create a cache node.
#
# @param name The functor.
# @constructor The new cache node.
##
class Cache:
    def __init__(self, name):
        self.link = NotImplemented
        self.name = name


###
# Check whether an object is a cache.
#
# @param obj The object.
# @return True if the object is a cache, otherwise false.
##
def is_cache(obj):
    return isinstance(obj, Cache)


################################################################
# Snapshot Data                                                #
################################################################

def snapshot_peek(func):
    if is_stick(func):
        return snapshot_rope(func.rope)
    else:
        return snapshot_rope(func)


###
# Make snapshot of a logical.
#
# @param rope The logical.
# @return The clause list snapshot.
##
def snapshot_rope(rope):
    res = rope.cache
    if res is None:
        res = [NotImplemented] * rope.count
        copy_rope(res, rope)
        rope.cache = res
    return res


def copy_rope(res, rope):
    if isinstance(rope.data, list):
        data = rope.data
        j = 0
        i = 0
        while i < len(data):
            clause = data[i]
            if clause.remover is NotImplemented:
                res[j] = clause
                j += 1
            i += 1
    else:
        data = rope.data
        j = 0
        for clause in data.keys():
            if clause.remover is NotImplemented:
                res[j] = clause
                j += 1


################################################################
# Linked Provables                                             #
################################################################

###
# Retrieve a provable from monomorphic cache.
#
# @param cache The cache.
# @param arity The arity.
# @return The provable or NotImplemented
##
def ensure_link(cache, arity):
    peek = cache.link
    if peek is NotImplemented or peek.remover is not NotImplemented:
        peek = pred_link(cache.name, arity)
        cache.link = peek
    return peek


def pred_link(functor, arity):
    if arity < 0:
        return NotImplemented
    temp = kb.get(functor, NotImplemented)
    if temp is NotImplemented:
        return NotImplemented
    peek = (temp[arity] if arity < len(temp) else NotImplemented)
    if peek is NotImplemented or peek.remover is not NotImplemented:
        return NotImplemented
    return peek


def resolve_link(functor, arity):
    if is_cache(functor):
        return ensure_link(functor, arity)
    elif is_atom(functor):
        return pred_link(functor, arity)
    elif is_provable(functor):
        return functor
    else:
        check_nonvar(functor)
        functor = copy_term(functor)
        raise make_error(Compound("type_error",
                                  ["callable", functor]))


###
# Assure that the object is a nonvar.
#
# @param beta The object.
##
def check_nonvar(beta):
    if is_variable(beta):
        raise make_error("instantiation_error")


################################################################
# Dynamic Predicates                                           #
################################################################

###
# Retrieve or create a provable from monomorphic cache.
#
# @param cache The cache.
# @param arity The arity.
# @param flags The flags.
# @return The provable
##
def ensure_touch(cache, arity, flags):
    peek = cache.link
    if peek is NotImplemented or peek.remover is not NotImplemented:
        peek = pred_touch(cache.name, arity, flags)
        cache.link = peek
    return peek


def pred_touch(functor, arity, flags):
    temp = kb.get(functor, NotImplemented)
    if temp is NotImplemented:
        temp = []
        kb[functor] = temp
    peek = (temp[arity] if arity < len(temp) else NotImplemented)
    if peek is NotImplemented or peek.remover is not NotImplemented:
        res = make_defined(VOID_ARGS)
        if peek is not NotImplemented:
            res.overlay = peek
        if (flags & MASK_TOUCH_DYNAMIC) != 0:
            res.flags |= MASK_PRED_DYNAMIC
        while arity >= len(temp):
            temp.append(NotImplemented)
        temp[arity] = res
        peek = res
    else:
        if not is_logical(peek.func) and not is_stick(peek.func):
            raise make_error(Compound("permission_error",
                                      ["modify", "static_procedure",
                                       make_indicator(functor, arity)]))
        if (flags & MASK_TOUCH_DYNAMIC) != 0:
            if (peek.flags & MASK_PRED_DYNAMIC) == 0:
                raise make_error(Compound("permission_error",
                                          ["modify", "static_procedure",
                                           make_indicator(functor, arity)]))
    if (flags & MASK_TOUCH_PREHASH) != 0:
        if (peek.flags & MASK_PRED_PREHASH) == 0:
            if is_stick(peek.func):
                peek.func = peek.func.rope
            peek.flags |= MASK_PRED_PREHASH
    return peek


def resolve_touch(functor, arity, flags):
    if is_cache(functor):
        return ensure_touch(functor, arity, flags)
    elif is_atom(functor):
        return pred_touch(functor, arity, flags)
    elif is_provable(functor):
        return functor
    else:
        check_nonvar(functor)
        functor = copy_term(functor)
        raise make_error(Compound("type_error",
                                  ["callable", functor]))


################################################################
# Index Extension                                              #
################################################################

###
# The function returns an anonymous predicate for the given clauses.
# The index is not yet built, so only a logical is stored.
#
# @param data The clauses.
# @return The predicate.
##
def make_defined(data):
    peek = Provable()
    peek.func = new_rope()
    i = 0
    while i < len(data):
        add_peek(peek.func, 0, data[i], MASK_TOUCH_BOTTOM, peek.flags)
        i += 1
    return peek


def new_rope():
    return Logical(None, 0, [])


def sanitize_key(key):
    if isinstance(key, dict) or isinstance(key, list):
        return id(key)
    else:
        return key


def new_bouquet(rope, width):
    guards = [NotImplemented] * width
    maps = [NotImplemented] * width
    return Stick(rope, guards, maps)


def extend_bouquet(peek, j, offset, rope, flags):
    peek.guards[j] = new_rope()
    peek.maps[j] = {}
    if isinstance(rope.data, list):
        data = rope.data
        i = 0
        while i < len(data):
            clause = data[i]
            if clause.remover is NotImplemented:
                add_map(peek, j, offset, clause, MASK_TOUCH_BOTTOM, flags)
            i += 1
    else:
        data = rope.data
        for clause in data.keys():
            if clause.remover is NotImplemented:
                add_map(peek, j, offset, clause, MASK_TOUCH_BOTTOM, flags)


################################################################
# Clauses Retrieval                                            #
################################################################

###
# Retrieve a logical from a provable possibly using an index.
# If only a logical is stored, build an index before retrieval.
#
# @param peek The predicate.
# @param args The actual arguments.
# @return The logical.
##
def defined_pred(peek, args):
    width = min(MAX_INDEX, len(args))
    offset = 0
    func = peek.func
    flags = peek.flags
    val = None
    k = 0
    while True:
        if is_stick(func):
            rope = func.rope
        else:
            rope = func
        if rope.count < 2:
            return rope
        i = 0
        while i < width:
            key = key_value(args[i+offset], flags)
            if key is NotImplemented:
                i += 1
                continue
            if not is_stick(func):
                func = new_bouquet(rope, width)
                if is_stick(peek):
                    if val is NotImplemented:
                        peek.guards[k] = func
                    else:
                        peek.maps[k][val] = func
                else:
                    peek.func = func
            peek = func
            if peek.maps[i] is NotImplemented:
                extend_bouquet(peek, i, offset, rope, flags)
            if len(peek.maps[i]) == 0:
                i += 1
                continue
            key = sanitize_key(key)
            func = peek.maps[i].get(key, NotImplemented)
            if func is NotImplemented:
                func = peek.guards[i]
                val = NotImplemented
            else:
                val = key
            k = i
            width = width-i-1
            offset = i+offset+1
            i = -1
            break
        if not i < width:
            return rope


def key_value(term, flags):
    term = deref(term)
    if not is_variable(term):
        if (flags & MASK_PRED_PREHASH) != 0:
            if is_frozen(term):
                term = term.hash
            elif not is_compound(term):
                term = object_hash_code(term)
            else:
                term = NotImplemented
        else:
            if is_structure(term):
                term = term.functor
    else:
        term = NotImplemented
    return term


# Avoid cyclic import member error
from nova.machine import (
    is_frozen, object_hash_code,
    is_atom, make_error, make_indicator, VOID_ARGS)


################################################################
# Destroy Provable                                            #
################################################################

###
# Remove a predicate from the knowledge base.
#
# @param functor The functor.
# @param arity The arity.
##
def pred_destroy(functor, arity):
    temp = kb.get(functor, NotImplemented)
    if temp is NotImplemented:
        return
    peek = (temp[arity] if arity < len(temp) else NotImplemented)
    if peek is NotImplemented or peek.remover is not NotImplemented:
        return
    if peek.creator == stage:
        peek = clear_pop(peek)
        temp[arity] = peek
        if peek is NotImplemented and trim_arities(temp):
            del kb[functor]
    else:
        peek.remover = stage


###
# Clear and pop a provable.
#
# @param peek The provable.
# @return The parent provable.
##
def clear_pop(peek):
    peek.remover = stage
    peek.func = NotImplemented

    back = peek
    peek = back.overlay
    back.overlay = NotImplemented
    return peek


###
# Trim the arities array.
#
# @param peek The arities array.
# @return boolean True if empty, otherwise fale.
##
def trim_arities(peek):
    pos = len(peek)
    while pos > 0 and peek[pos-1] is NotImplemented:
        pos -= 1
    if pos == 0:
        return True
    if pos != len(peek):
        del peek[pos:]
    return False


################################################################
# Clauses Transactions                                         #
################################################################

###
# Rollback the clauses.
##
def clear():
    for functor in list(kb):
        temp = kb[functor]
        i = 0
        while i < len(temp):
            peek = temp[i]
            if peek is NotImplemented:
                i += 1
                continue
            if peek.creator == stage:
                peek = clear_pop(peek)
                temp[i] = peek
                if peek is NotImplemented:
                    i += 1
                    continue
            if peek.remover == stage:
                peek.remover = NotImplemented
            if is_logical(peek.func) or is_stick(peek.func):
                rollback_peek(peek.func, True)
            i += 1
        if trim_arities(temp):
            del kb[functor]


def rollback_peek(peek, update):
    if is_stick(peek):
        if not has_action(peek.rope):
            return
        i = 0
        while i < len(peek.maps):
            temp = peek.maps[i]
            if temp is NotImplemented:
                i += 1
                continue
            for key, val in list(temp.items()):
                rollback_peek(val, False)
                if size_peek(val) == 0:
                    del temp[key]
            rollback_peek(peek.guards[i], False)
            i += 1
        rollback_rope(peek.rope, update)
    else:
        if not has_action(peek):
            return
        rollback_rope(peek, update)


def size_peek(func):
    if is_stick(func):
        rope = func.rope
    else:
        rope = func
    if isinstance(rope.data, list):
        return len(rope.data)
    else:
        return len(rope.data)


###
# Check whether a logical has some action.
#
# @param rope The logical.
# @return True if the logical has some action, false otherwise.
##
def has_action(rope):
    if isinstance(rope.data, list):
        data = rope.data
        i = 0
        while i < len(data):
            clause = data[i]
            if clause.creator == stage:
                return True
            if clause.remover == stage:
                return True
            i += 1
        return False
    else:
        data = rope.data
        for clause in data.keys():
            if clause.creator == stage:
                return True
            if clause.remover == stage:
                return True
        return False


###
# Rollback clauses from a logical.
#
# @param rope The logical.
# @param update The update flag.
##
def rollback_rope(rope, update):
    if isinstance(rope.data, list):
        data = rope.data
        j = 0
        i = 0
        while i < len(data):
            clause = data[i]
            if clause.creator == stage:
                rope.count -= 1
            else:
                if clause.remover == stage:
                    if update:
                        clause.remover = NotImplemented
                    rope.count += 1
                data[j] = clause
                j += 1
            i += 1
        del data[j:]
        rope.cache = None
    else:
        data = rope.data
        for clause in list(data.keys()):
            if clause.creator == stage:
                rope.count -= 1
                del data[clause]
            else:
                if clause.remover == stage:
                    if update:
                        clause.remover = NotImplemented
                    rope.count += 1
        rope.cache = None


################################################################
# Provable Addition                                            #
################################################################

###
# Enhance the knowledge base by a provable.
#
# @param functor The functor.
# @param arity The arity.
# @param pred The provable.
##
def set(functor, arity, pred):
    temp = kb.get(functor, NotImplemented)
    if temp is NotImplemented:
        temp = []
        kb[functor] = temp
    peek = (temp[arity] if arity < len(temp) else NotImplemented)
    if peek is NotImplemented or peek.remover is not NotImplemented:
        if peek is not NotImplemented:
            pred.overlay = peek
        while arity >= len(temp):
            temp.append(NotImplemented)
        temp[arity] = pred
    else:
        raise make_error(Compound("permission_error",
            ["coerce", "procedure", make_indicator(functor, arity)]))


################################################################
# Clause Addition                                              #
################################################################

###
# Enhance the knowledge base by a clause.
#
# @param arity The arity.
# @param clause The clause.
##
def add(clause):
    add_clause(clause, MASK_TOUCH_BOTTOM)


def add_clause(clause, flags):
    if clause.remover is not NotImplemented:
        raise make_error(Compound("permission_error",
            ["modify", "static_procedure",
               make_indicator(clause.functor, len(clause.head))]))
    if clause.creator is not NotImplemented:
        return
    peek = resolve_touch(clause.functor, len(clause.head), flags)
    add_peek(peek.func, 0, clause, flags, peek.flags)
    clause.creator = stage
    if (flags & MASK_TOUCH_DYNAMIC) == 0:
        clause.shard = engine.partition


def add_peek(peek, offset, clause, flags, flags2):
    if is_stick(peek):
        add_rope(peek.rope, clause, flags)
        i = 0
        while i < len(peek.maps):
            if peek.maps[i] is not NotImplemented:
                add_map(peek, i, offset, clause, flags, flags2)
            i += 1
    else:
        add_rope(peek, clause, flags)


def add_map(peek, i, offset, clause, flags, flags2):
    key = index_value(clause.head[i+offset], clause.body, flags2)
    temp = peek.maps[i]
    if key is NotImplemented:
        for key, val in temp.items():
            add_peek(val, i+offset+1, clause, flags, flags2)
        add_peek(peek.guards[i], i+offset+1, clause, flags, flags2)
    else:
        key = sanitize_key(key)
        val = temp.get(key, NotImplemented)
        if val is NotImplemented:
            val = clone_peek(peek.guards[i])
            temp[key] = val
        add_peek(val, i+offset+1, clause, flags, flags2)


def add_rope(rope, clause, flags):
    if isinstance(rope.data, list):
        data = rope.data
        if (flags & MASK_TOUCH_BOTTOM) != 0:
            data.append(clause)
        else:
            data.insert(0, clause)
        if len(data) >= ROPE_HIGH:
            rope.data = OrderedDict.fromkeys(data, True)
        rope.count += 1
        rope.cache = None
    else:
        data = rope.data
        if (flags & MASK_TOUCH_BOTTOM) != 0:
            data[clause] = True
        else:
            data[clause] = True
            data.move_to_end(clause, last=False)
        rope.count += 1
        rope.cache = None


def clone_peek(func):
    if is_stick(func):
        rope = func.rope
    else:
        rope = func
    if isinstance(rope.data, list):
        return Logical(rope.cache, rope.count, list(rope.data))
    else:
        return Logical(rope.cache, rope.count, OrderedDict(rope.data))


################################################################
# Clause Removal                                               #
################################################################

###
# Remove a clause from the knowledge base.
#
# @param clause The clause.
# @param flags The flags.
# @return True if the clause was removed, false otherwise.
##
def remove_clause(clause, flags):
    if clause.remover is not NotImplemented:
        return False
    if clause.creator is NotImplemented:
        return False
    peek = resolve_link(clause.functor, len(clause.head))
    if peek is NotImplemented:
        return False
    if not is_logical(peek.func) and not is_stick(peek.func):
        raise make_error(Compound("permission_error",
              ["modify", "static_procedure",
                    make_indicator(clause.functor, len(clause.head))]))
    remove_peek(peek.func, 0, clause, flags, peek.flags)
    if clause.creator != stage:
        clause.remover = stage
    else:
        clause.creator = NotImplemented
    return True


def remove_peek(peek, offset, clause, flags, flags2):
    if is_stick(peek):
        remove_rope(peek.rope, clause, flags)
        i = 0
        while i < len(peek.maps):
            temp = peek.maps[i]
            if temp is NotImplemented:
                i += 1
                continue
            key = index_value(clause.head[i+offset], clause.body, flags2)
            if key is NotImplemented:
                for key, val in list(temp.items()):
                    remove_peek(val, i+offset+1, clause, flags, flags2)
                    if size_peek(val) == 0:
                        del temp[key]
                remove_peek(peek.guards[i], i+offset+1, clause, flags, flags2)
            else:
                key = sanitize_key(key)
                val = temp.get(key)
                remove_peek(val, i+offset+1, clause, flags, flags2)
                if size_peek(val) == 0:
                    del temp[key]
            i += 1
    else:
        remove_rope(peek, clause, flags)


def remove_rope(rope, clause, flags):
    if isinstance(rope.data, list):
        data = rope.data
        if (flags & MASK_REMOVE_REVERSE) == 0:
            index = array_index(data, clause)
        else:
            index = array_last_index(data, clause)
        if clause.creator == stage:
            if index == -1:
                raise Exception("rope corrupted")
            del data[index]
        else:
            if index == -1:
                raise Exception("rope corrupted")
        rope.count -= 1
        rope.cache = None
    else:
        data = rope.data
        if clause.creator == stage:
            if data.pop(clause, NotImplemented) is NotImplemented:
                raise Exception("rope corrupted")
        else:
            if not clause in data:
                raise Exception("rope corrupted")
        if len(data) < ROPE_LOW:
            rope.data = list(data.keys())
        rope.count -= 1
        rope.cache = None


def array_index(arr, obj):
    i = 0
    while i < len(arr):
        if arr[i] is obj:
            return i
        i += 1
    return -1


def array_last_index(arr, obj):
    i = len(arr)
    while i > 0:
        i -= 1
        if arr[i] is obj:
            return i
    return -1
