Function simplicity_verifyCanonicalOrder

src/simplicity/dag.c:380–469

Verifies that the 'dag' is in canonical order, meaning that nodes under the left branches have lower indices than nodes under * right branches, with the exception that nodes under right branches may (cross-)reference identical nodes that already occur under * left branches. * * Returns 'SIMPLICITY_NO_ERROR' if the 'dag' is in canonical order, and returns 'SIMPLICITY_ERR_DATA_OUT_OF_ORDER' if i

 * Precondition: dag_node dag[len] and 'dag' is well-formed.
 */
simplicity_err simplicity_verifyCanonicalOrder(dag_node* dag, const uint_fast32_t len) {
  uint_fast32_t bottom = 0;
  uint_fast32_t top = len-1; /* Underflow is checked below. */

  if (!len) {
    simplicity_assert(false); /* A well-formed dag has non-zero length */
    return SIMPLICITY_NO_ERROR; /* However, an empty dag is technically in canonical order */
  }

  /* We use dag[i].aux as a "stack" to manage the traversal of the DAG. */
  dag[top].aux = len; /* We will set top to 'len' to indicate we are finished. */

  /* Each time any particular 'top' value is revisited in this loop, bottom has increased to be strictly larger than the last 'child'
     value examined.  Therefore we will make further progress in the loop the next time around.
     By this reasoning any given 'top' value will be visited no more than numChildren(dag[top].tag) + 1 <= 3 times.
     Thus this loop iterates at most O('len') times.
   */
  while (top < len) {
    /* We determine canonical order by iterating through the dag in canonical (pre-)order,
       incrementing 'bottom' each time we encounter a node that is (correctly) placed at the 'bottom' index.
       We take advantage of the precondition that the dag is well-formed to know in advance that any children
       of a node have index strictly less than the node itself.
     */

    /* Check first child. */
    uint_fast32_t child = dag[top].child[0];
    switch (dag[top].tag) {
     case ASSERTL:
     case ASSERTR:
     case CASE:
     case DISCONNECT:
     case COMP:
     case PAIR:
     case INJL:
     case INJR:
     case TAKE:
     case DROP:
      if (bottom < child) {
        dag[child].aux = top;
        top = child;
        continue;
      }
      if (bottom == child) bottom++;
     case IDEN:
     case UNIT:
     case WITNESS:
     case HIDDEN:
     case JET:
     case WORD:
      break;
    }

    /* Check second child. */
    child = dag[top].child[1];
    switch (dag[top].tag) {
     case ASSERTL:
     case ASSERTR:
     case CASE: