/*
* SPDX-FileCopyrightText: (c) 2024 Chris Pressey, Cat's Eye Technologies
*
* SPDX-License-Identifier: LicenseRef-BSD-2-Clause-X-Collapsiv
*/
#include <assert.h>
#include <stdio.h>
#include "collapsiv.h"
#undef DEBUG
#define STACK_SIZE 1024
#define TERM_TYPE_POINTER 0
#define TERM_TYPE_ATOM 1
#define TERM_TYPE_CTOR 2
typedef struct {
int type;
union {
int pointer; /* Index into the stack. */
char atom; /* An atom is a single character (for now) */
int arity; /* Number of subterms this term has. They are stored in the stack
* entries directly below this one. But note they may take up more
* than `arity` number of stack cells, as they too might be ctors
* with their own subterms. Note that the "function symbol" or
* "constructor" is generally assumed to be an atom, but might NOT
* be an atom, and IS included in the arity. So these are something
* like S-expressions in their structure.
*/
} data;
} StackEntry;
StackEntry stack[STACK_SIZE];
int sp = 0;
/* FORWARD DECLARATIONS */
void deduplicate_top(void);
/*
* Push an atom onto the stack
*/
void push_atom(char atom) {
assert(sp < STACK_SIZE);
stack[sp].type = TERM_TYPE_ATOM;
stack[sp].data.atom = atom;
sp++;
deduplicate_top();
}
/*
* Is the stack entry at this position an atom?
*/
int is_atom(int index) {
return stack[index].type == TERM_TYPE_ATOM;
}
/*
* Push a pointer onto the stack
*/
void push_pointer(int index) {
assert(sp < STACK_SIZE);
stack[sp].type = TERM_TYPE_POINTER;
stack[sp].data.pointer = index;
sp++;
}
/*
* Is the stack entry at this position a pointer?
*/
int is_pointer(int index) {
return stack[index].type == TERM_TYPE_POINTER;
}
/*
* Make a ctor term with given arity.
*/
void make_ctor(int arity) {
assert(sp < STACK_SIZE);
assert(arity >= 1);
stack[sp].type = TERM_TYPE_CTOR;
stack[sp].data.arity = arity;
sp++;
deduplicate_top();
}
/*
* Is the stack entry at this position a constructor?
*/
int is_ctor(int index) {
return stack[index].type == TERM_TYPE_CTOR;
}
/*
* Given the index of a term on the stack, return how many stack cells
* it occupies. Note that this must be computed recursively in the case
* of ctors as they may have subterms which are themselves ctors.
* Note also that we do *not* follow pointers; we measure the space they
* themselves are taking up.
*/
int term_size(int index) {
if (is_atom(index) || is_pointer(index)) {
return 1;
} else if (is_ctor(index)) {
int probe = index - 1;
int sz;
int total = 1; /* one cell for the CTOR / arity cell! */
for (int i = 0; i < stack[index].data.arity; i++) {
sz = term_size(probe);
total += sz;
probe -= sz;
}
return total;
} else {
assert(is_atom(index) || is_pointer(index) || is_ctor(index));
return 0;
}
}
/*
* Remove the top term from the stack.
*/
void pop(void) {
assert(sp > 0);
int sz = term_size(sp - 1);
sp -= sz;
}
/*
* Structurally compare the terms at src_index and dest_index
* (following pointers and ignoring them as part of the structure)
* and return 1 if they are identical, 0 otherwise.
*/
int compare_terms(int src_index, int dest_index) {
/* Follow pointers to get to the actual terms */
while (is_pointer(src_index)) {
src_index = stack[src_index].data.pointer;
}
while (is_pointer(dest_index)) {
dest_index = stack[dest_index].data.pointer;
}
/* Compare the terms */
if (stack[src_index].type != stack[dest_index].type) {
return 0;
}
switch (stack[src_index].type) {
case TERM_TYPE_ATOM:
return stack[src_index].data.atom == stack[dest_index].data.atom;
case TERM_TYPE_CTOR:
if (stack[src_index].data.arity != stack[dest_index].data.arity) {
return 0;
}
/* Compare subterms */
int src_probe = src_index - 1;
int dest_probe = dest_index - 1;
for (int i = 1; i <= stack[src_index].data.arity; i++) {
if (!compare_terms(src_probe, dest_probe)) {
return 0;
}
src_probe -= term_size(src_probe);
dest_probe -= term_size(dest_probe);
}
return 1;
default:
assert(0); /* Should never reach here */
return 0;
}
}
/*
* Compare the term at src_index with the term at dest_index,
* in a depth-first fashion: if the dest term is a composite
* term, recursively compare the src term with each of the
* dest term's children, before comparing the src term with
* the dest term itself. Return the index of any term that
* was found to be equal. If none was found, return -1.
*/
int compare_terms_deep(int src_index, int dest_index) {
/* Follow pointers to get to the actual terms */
while (is_pointer(src_index)) {
src_index = stack[src_index].data.pointer;
}
while (is_pointer(dest_index)) {
dest_index = stack[dest_index].data.pointer;
}
/* If dest_index is a constructor, recursively compare with its children */
if (stack[dest_index].type == TERM_TYPE_CTOR) {
int probe = dest_index - 1;
for (int i = 0; i < stack[dest_index].data.arity; i++) {
int result = compare_terms_deep(src_index, probe);
if (result >= 0) {
return result;
}
probe -= term_size(probe);
}
}
/* If no match found in children (or if dest is not a constructor),
* perform a shallow comparison
*/
if (compare_terms(src_index, dest_index)) {
return dest_index;
}
return -1;
}
/*
* Find a term on the stack that is identical to the term at index.
* Return its index. If there is none, return -1.
*/
void deduplicate(int index) {
int tindex = index;
int result = -1;
do {
tindex -= term_size(tindex);
if (tindex >= 0) {
result = compare_terms_deep(index, tindex);
#ifdef DEBUG
if (result > 0) {
printf("compared terms at [%d] and [%d] and found match at [%d]:\n", index, tindex, result);
print_term(index, 0);
print_term(tindex, 0);
print_term(result, 0);
printf("\n");
}
#endif
}
} while(result < 0 && tindex >= 0);
if (result > 0) {
pop();
push_pointer(result);
}
}
/*
* Find a term on the stack that is identical to the term at the top.
*/
void deduplicate_top(void) {
assert(sp > 0);
deduplicate(sp - 1);
}
/*
* Duplicate the top stack entry
*/
void dup(void) {
assert(sp > 0);
assert(sp < STACK_SIZE);
push_pointer(sp - 1);
}
/*
* *********** DEBUGGING AND TESTING *************
*/
void print_term(int index, int depth) {
for (int i = 0; i < depth; i++) {
printf(" ");
}
if (stack[index].type == TERM_TYPE_ATOM) {
printf("[%d] Atom: %c\n", index, stack[index].data.atom);
} else if (stack[index].type == TERM_TYPE_POINTER) {
printf("[%d] --->\n", index);
print_term(stack[index].data.pointer, depth);
} else if (stack[index].type == TERM_TYPE_CTOR) {
printf("[%d] Ctor: %d(\n", index, stack[index].data.arity);
int probe = index - 1;
int sz;
for (int i = 0; i < stack[index].data.arity; i++) {
sz = term_size(probe);
print_term(probe, depth + 1);
probe -= sz;
}
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf(")\n");
}
}
void dump_stack(void) {
printf("Stack dump (size: %d):\n", sp);
if (sp == 0) return;
int probe = sp - 1;
int sz;
while (probe >= 0) {
sz = term_size(probe);
print_term(probe, 0);
probe -= sz;
}
printf("\n");
}
void reset_stack(void) {
sp = 0;
}
int get_stack_pointer(void) {
return sp;
}
int get_stack_entry_type(int index) {
return stack[index].type;
}
char get_stack_entry_atom(int index) {
assert(stack[index].type == TERM_TYPE_ATOM);
return stack[index].data.atom;
}
int get_stack_entry_pointer(int index) {
assert(stack[index].type == TERM_TYPE_POINTER);
return stack[index].data.pointer;
}
int get_stack_entry_arity(int index) {
assert(stack[index].type == TERM_TYPE_CTOR);
return stack[index].data.arity;
}