/*

 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")

 *

 * SPDX-License-Identifier: MPL-2.0

 *

 * This Source Code Form is subject to the terms of the Mozilla Public

 * License, v. 2.0. If a copy of the MPL was not distributed with this

 * file, you can obtain one at https://mozilla.org/MPL/2.0/.

 *

 * See the COPYRIGHT file distributed with this work for additional

 * information regarding copyright ownership.

 */

#include <assert.h>

#include <stdint.h>

#include <stdio.h>

#include <isc/buffer.h>

#include <isc/loop.h>

#include <isc/magic.h>

#include <isc/refcount.h>

#include <isc/rwlock.h>

#include <isc/urcu.h>

#include <isc/util.h>

#include <dns/db.h>

#include <dns/fixedname.h>

#include <dns/name.h>

#include <dns/qp.h>

#include <dns/types.h>

#include "qp_p.h"

#include <tests/qp.h>

/***********************************************************************

 *

 *  key reverse conversions

 */

uint8_t

qp_test_bittoascii(dns_qpshift_t bit) {

  uint8_t byte = dns_qp_byte_for_bit[bit];

  if (bit == SHIFT_NOBYTE) {

    return '.';

  } else if (qp_common_character(byte)) {

    return byte;

  } else if (byte < '-') {

    return '#';

  } else if (byte < '_') {

    return '@';

  } else {

    return '~' - SHIFT_OFFSET + bit;

  }

}

const char *

qp_test_keytoascii(dns_qpkey_t key, size_t len) {

  for (size_t offset = 1; offset < len; offset++) {

    key[offset] = qp_test_bittoascii(key[offset]);

  }

  key[len] = '\0';

  return (const char *)key;

}

/***********************************************************************

 *

 *  trie properties

 */

static size_t

getheight(dns_qp_t *qp, dns_qpnode_t *n) {

  if (node_tag(n) == LEAF_TAG) {

    return 0;

  }

  size_t max_height = 0;

  dns_qpnode_t *twigs = branch_twigs(qp, n);

  dns_qpweight_t size = branch_twigs_size(n);

  for (dns_qpweight_t pos = 0; pos < size; pos++) {

    size_t height = getheight(qp, &twigs[pos]);

    max_height = ISC_MAX(max_height, height);

  }

  return max_height + 1;

}

size_t

qp_test_getheight(dns_qp_t *qp) {

  dns_qpnode_t *root = get_root(qp);

  return root == NULL ? 0 : getheight(qp, root);

}

static size_t

maxkeylen(dns_qp_t *qp, dns_qpnode_t *n) {

  if (node_tag(n) == LEAF_TAG) {

    dns_qpkey_t key;

    return leaf_qpkey(qp, n, key);

  }

  size_t max_len = 0;

  dns_qpnode_t *twigs = branch_twigs(qp, n);

  dns_qpweight_t size = branch_twigs_size(n);

  for (dns_qpweight_t pos = 0; pos < size; pos++) {

    size_t len = maxkeylen(qp, &twigs[pos]);

    max_len = ISC_MAX(max_len, len);

  }

  return max_len;

}

size_t

qp_test_maxkeylen(dns_qp_t *qp) {

  dns_qpnode_t *root = get_root(qp);

  return root == NULL ? 0 : maxkeylen(qp, root);

}

/***********************************************************************

 *

 *  dump to stdout

 */

static void

dumpread(dns_qpreadable_t qpr, const char *type, const char *tail) {

  dns_qpreader_t *qp = dns_qpreader(qpr);

  printf("%s %p root %u %u:%u base %p methods %p%s", type, qp,

         qp->root_ref, ref_chunk(qp->root_ref), ref_cell(qp->root_ref),

         qp->base, qp->methods, tail);

}

static void

dumpqp(dns_qp_t *qp, const char *type) {

  dumpread(qp, type, " mctx ");

  printf("%p\n", qp->mctx);

  printf("%s %p usage %p chunk_max %u bump %u fender %u\n", type, qp,

         qp->usage, qp->chunk_max, qp->bump, qp->fender);

  printf("%s %p leaf %u live %u used %u free %u hold %u\n", type, qp,

         qp->leaf_count, qp->used_count - qp->free_count, qp->used_count,

         qp->free_count, qp->hold_count);

  printf("%s %p compact_all=%d transaction_mode=%d write_protect=%d\n",

         type, qp, qp->compact_all, qp->transaction_mode,

         qp->write_protect);

}

void

qp_test_dumpread(dns_qpreadable_t qp) {

  dumpread(qp, "qpread", "\n");

  fflush(stdout);

}

void

qp_test_dumpsnap(dns_qpsnap_t *qp) {

  dumpread(qp, "qpsnap", " whence ");

  printf("%p\n", qp->whence);

  fflush(stdout);

}

void

qp_test_dumpqp(dns_qp_t *qp) {

  dumpqp(qp, "qp");

  fflush(stdout);

}

void

qp_test_dumpmulti(dns_qpmulti_t *multi) {

  dns_qpreader_t qpr;

  dns_qpnode_t *reader = rcu_dereference(multi->reader);

  dns_qpmulti_t *whence = unpack_reader(&qpr, reader);

  dumpqp(&multi->writer, "qpmulti->writer");

  printf("qpmulti->reader %p root_ref %u %u:%u base %p\n", reader,

         qpr.root_ref, ref_chunk(qpr.root_ref), ref_cell(qpr.root_ref),

         qpr.base);

  printf("qpmulti->reader %p whence %p\n", reader, whence);

  unsigned int snapshots = 0;

  ISC_LIST_FOREACH(multi->snapshots, snap, link) {

    snapshots++;

  }

  printf("qpmulti %p snapshots %u\n", multi, snapshots);

  fflush(stdout);

}

void

qp_test_dumpchunks(dns_qp_t *qp) {

  dns_qpcell_t used_count = 0;

  dns_qpcell_t free_count = 0;

  dumpqp(qp, "qp");

  for (dns_qpchunk_t c = 0; c < qp->chunk_max; c++) {

    printf("qp %p chunk %u base %p "

           "used %u free %u immutable %u discounted %u\n",

           qp, c, qp->base->ptr[c], qp->usage[c].used,

           qp->usage[c].free, qp->usage[c].immutable,

           qp->usage[c].discounted);

    used_count += qp->usage[c].used;

    free_count += qp->usage[c].free;

  }

  printf("qp %p total used %" PRIu32 " free %" PRIu32 "\n", qp,

         used_count, free_count);

  fflush(stdout);

}

void

qp_test_dumptrie(dns_qpreadable_t qpr) {

  dns_qpreader_t *qp = dns_qpreader(qpr);

  struct {

    dns_qpref_t ref;

    dns_qpshift_t max, pos;

  } stack[512];

  size_t sp = 0;

  dns_qpcell_t leaf_count = 0;

  /*

   * fake up a sentinel stack entry corresponding to the root

   * node; the ref is deliberately out of bounds, and pos == max

   * so we will immediately stop scanning it

   */

  stack[sp].ref = INVALID_REF;

  stack[sp].max = 0;

  stack[sp].pos = 0;

  dns_qpnode_t *n = get_root(qp);

  if (n == NULL) {

    printf("%p EMPTY\n", n);

    fflush(stdout);

    return;

  } else {

    printf("%p ROOT qp %p base %p\n", n, qp, qp->base);

  }

  for (;;) {

    if (is_branch(n)) {

      dns_qpref_t ref = branch_twigs_ref(n);

      dns_qpweight_t max = branch_twigs_size(n);

      dns_qpnode_t *twigs = ref_ptr(qp, ref);

      /* brief list of twigs */

      dns_qpkey_t bits;

      size_t len = 0;

      for (dns_qpshift_t bit = SHIFT_NOBYTE;

           bit < SHIFT_OFFSET; bit++)

      {

        if (branch_has_twig(n, bit)) {

          bits[len++] = bit;

        }

      }

      assert(len == max);

      qp_test_keytoascii(bits, len);

      printf("%*s%p BRANCH %p %u %u:%u %zu %s\n", (int)sp * 2,

             "", n, twigs, ref, ref_chunk(ref), ref_cell(ref),

             branch_key_offset(n), bits);

      ++sp;

      stack[sp].ref = ref;

      stack[sp].max = max;

      stack[sp].pos = 0;

    } else {

      dns_qpkey_t key;

      qp_test_keytoascii(key, leaf_qpkey(qp, n, key));

      printf("%*s%p LEAF %p %d %s\n", (int)sp * 2, "", n,

             leaf_pval(n), leaf_ival(n), key);

      leaf_count++;

    }

    while (stack[sp].pos == stack[sp].max) {

      if (sp == 0) {

        printf("LEAVES %d\n", leaf_count);

        fflush(stdout);

        return;

      }

      --sp;

    }

    stack[sp].pos++;

    fprintf(stderr, "pos %d/%d, ref+%d\n", stack[sp].pos,

      stack[sp].max, stack[sp].pos - 1);

    n = ref_ptr(qp, stack[sp].ref) + stack[sp].pos - 1;

  }

}

static void

dumpdot_name(dns_qpnode_t *n) {

  if (n == NULL) {

    printf("empty");

  } else if (is_branch(n)) {

    dns_qpref_t ref = branch_twigs_ref(n);

    printf("c%dn%d", ref_chunk(ref), ref_cell(ref));

  } else {

    printf("v%p", leaf_pval(n));

  }

}

static void

dumpdot_twig(dns_qp_t *qp, dns_qpnode_t *n) {

  if (n == NULL) {

    printf("empty [shape=oval, label=\"\\N EMPTY\"];\n");

  } else if (is_branch(n)) {

    dumpdot_name(n);

    printf(" [shape=record, label=\"{ \\N\\noff %zu | ",

           branch_key_offset(n));

    char sep = '{';

    for (dns_qpshift_t bit = SHIFT_NOBYTE; bit < SHIFT_OFFSET;

         bit++)

    {

      if (branch_has_twig(n, bit)) {

        printf("%c <t%d> %c ", sep,

               branch_twig_pos(n, bit),

               qp_test_bittoascii(bit));

        sep = '|';

      }

    }

    printf("}}\"];\n");

    dns_qpnode_t *twigs = branch_twigs(qp, n);

    dns_qpweight_t size = branch_twigs_size(n);

    for (dns_qpweight_t pos = 0; pos < size; pos++) {

      dumpdot_name(n);

      printf(":t%d:e -> ", pos);

      dumpdot_name(&twigs[pos]);

      printf(":w;\n");

    }

    for (dns_qpweight_t pos = 0; pos < size; pos++) {

      dumpdot_twig(qp, &twigs[pos]);

    }

  } else {

    dns_qpkey_t key;

    const char *str;

    str = qp_test_keytoascii(key, leaf_qpkey(qp, n, key));

    printf("v%p [shape=oval, label=\"\\N ival %d\\n%s\"];\n",

           leaf_pval(n), leaf_ival(n), str);

  }

}

void

qp_test_dumpdot(dns_qp_t *qp) {

  REQUIRE(QP_VALID(qp));

  dns_qpnode_t *n = get_root(qp);

  printf("strict digraph {\nrankdir = \"LR\"; ranksep = 1.0;\n");

  printf("ROOT [shape=point]; ROOT -> ");

  dumpdot_name(n);

  printf(":w;\n");

  dumpdot_twig(qp, n);

  printf("}\n");

}

void

qp_test_printkey(const dns_qpkey_t key, size_t keylen) {

  dns_fixedname_t fn;

  dns_name_t *n = dns_fixedname_initname(&fn);

  dns_namespace_t s;

  char txt[DNS_NAME_FORMATSIZE];

  dns_qpkey_toname(key, keylen, n, &s);

  dns_name_format(n, txt, sizeof(txt));

  printf("%s%s%s\n", txt,

         s == DNS_DBNAMESPACE_NSEC3

           ? "NSEC3:"

           : (s == DNS_DBNAMESPACE_NSEC ? "NSEC" : ""),

         dns_name_isabsolute(n) ? "." : "");

}

/**********************************************************************/