/*
  Copyright 2015-2016 David Anderson. All rights reserved.

  This program is free software; you can redistribute it and/or
  modify it under the terms of version 2 of the GNU General
  Public License as published by the Free Software Foundation.

  This program is distributed in the hope that it would be
  useful, but WITHOUT ANY WARRANTY; without even the implied
  warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  PURPOSE.

  Further, this software is distributed without any warranty
  that it is free of the rightful claim of any third person
  regarding infringement or the like.  Any license provided
  herein, whether implied or otherwise, applies only to this
  software file.  Patent licenses, if any, provided herein
  do not apply to combinations of this program with other
  software, or any other product whatsoever.

  You should have received a copy of the GNU General Public
  License along with this program; if not, write the Free
  Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
  Boston MA 02110-1301, USA.

*/

#include "globals.h"
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif /* HAVE_STDINT_H */
#include "dwarf_tsearch.h"
#include "macrocheck.h"
#include "esb.h"

#define TRUE 1
#define FALSE 0
/*  WARNING: the tree walk functions will, if presented **tree
    when *tree is wanted, simply find nothing. No error,
    just bad results. So when a walk produces nothing
    suspect a code mistake here.
    The basic problem is void* is a terrible way to
    pass in a pointer. But it's how tsearch was defined
    long ago.
*/

void *  macro_check_tree;    /* DWARF5 macros */
void *  macinfo_check_tree; /* DWARF 2,3,4 macros */

static struct Macrocheck_Map_Entry_s * macrocheck_map_insert(
    Dwarf_Unsigned off,
    unsigned prim,unsigned sec, void **map);
static struct Macrocheck_Map_Entry_s * macrocheck_map_find(
    Dwarf_Unsigned offset,
    void **map);
static void macrocheck_map_destroy(void *map);
static Dwarf_Unsigned macro_count_recs(void **base);

#ifdef SELFTEST
int failcount = 0;
struct glflags_s glflags;
#endif /* SELFTEST */


static struct Macrocheck_Map_Entry_s *
macrocheck_map_create_entry(Dwarf_Unsigned offset,
    unsigned add_primary, unsigned add_secondary)
{
    struct Macrocheck_Map_Entry_s *mp =
        (struct Macrocheck_Map_Entry_s *)
        calloc(1,sizeof(struct Macrocheck_Map_Entry_s));
    if (!mp) {
        return 0;
    }
    mp->mp_key = offset;
    mp->mp_len = 0;
    mp->mp_printed = 0;
    mp->mp_refcount_primary = add_primary;
    mp->mp_refcount_secondary = add_secondary;
    return mp;
}
static void
macrocheck_map_free_func(void *mx)
{
    struct Macrocheck_Map_Entry_s *m = mx;
    free(m);
}

static int
macrocheck_map_compare_func(const void *l, const void *r)
{
    const struct Macrocheck_Map_Entry_s *ml = l;
    const struct Macrocheck_Map_Entry_s *mr = r;
    if (ml->mp_key < mr->mp_key) {
        return -1;
    }
    if (ml->mp_key > mr->mp_key) {
        return 1;
    }
    return 0;
}

static struct Macrocheck_Map_Entry_s *
macrocheck_map_insert(Dwarf_Unsigned offset,
    unsigned add_prim,unsigned add_sec,void **tree1)
{
    void *retval = 0;
    struct Macrocheck_Map_Entry_s *re = 0;
    struct Macrocheck_Map_Entry_s *e;
    e  = macrocheck_map_create_entry(offset,add_prim,add_sec);
    /*  tsearch records e's contents unless e
        is already present . We must not free it till
        destroy time if it got added to tree1.  */
    retval = dwarf_tsearch(e,tree1, macrocheck_map_compare_func);
    if (retval) {
        re = *(struct Macrocheck_Map_Entry_s **)retval;
        if (re != e) {
            /*  We returned an existing record, e not needed.
                Increment refcounts. */
            re->mp_refcount_primary += add_prim;
            re->mp_refcount_secondary += add_sec;
            macrocheck_map_free_func(e);
        } else {
            /* Record e got added to tree1, do not free record e. */
        }
    }
    return NULL;
}

static struct Macrocheck_Map_Entry_s *
macrocheck_map_find(Dwarf_Unsigned offset,void **tree1)
{
    void *retval = 0;
    struct Macrocheck_Map_Entry_s *re = 0;
    struct Macrocheck_Map_Entry_s *e = 0;

    e = macrocheck_map_create_entry(offset,0,0);
    retval = dwarf_tfind(e,tree1, macrocheck_map_compare_func);
    if (retval) {
        re = *(struct Macrocheck_Map_Entry_s **)retval;
    }
    /*  The one we created here must be deleted, it is dead.
        We look at the returned one instead. */
    macrocheck_map_free_func(e);
    return re;
}

static void
macrocheck_map_destroy(void *map)
{
    /* tdestroy is not part of Posix. */
    dwarf_tdestroy(map,macrocheck_map_free_func);
}


void
add_macro_import(void **base,Dwarf_Bool is_primary,Dwarf_Unsigned offset)
{
    Dwarf_Unsigned prim_count  = 0;
    Dwarf_Unsigned sec_count  = 0;

    if(is_primary) {
        prim_count = 1;
    } else {
        sec_count = 1;
    }
    macrocheck_map_insert(offset,prim_count,sec_count,base);
}
void
add_macro_import_sup(UNUSEDARG void **base,
    UNUSEDARG Dwarf_Unsigned offset)
{
    /* FIXME */
    return;
}
void
add_macro_area_len(void **base, Dwarf_Unsigned offset,
    Dwarf_Unsigned len)
{
    struct Macrocheck_Map_Entry_s *re = 0;

    re = macrocheck_map_find(offset,base);
    if (re) {
        re->mp_len = len;
    }
}

static Dwarf_Unsigned reccount = 0;

static void
macro_walk_count_recs(UNUSEDARG const void *nodep,
    const DW_VISIT which,
    UNUSEDARG const int depth)
{
    if (which == dwarf_postorder || which == dwarf_endorder) {
        return;
    }
    reccount += 1;
}
static Dwarf_Unsigned
macro_count_recs(void **base)
{
    reccount = 0;
    dwarf_twalk(*base,macro_walk_count_recs);
    return reccount;
}

static Dwarf_Unsigned lowestoff = 0;
static Dwarf_Bool lowestfound = FALSE;
static void
macro_walk_find_lowest(const void *nodep,const DW_VISIT  which,
    UNUSEDARG const int  depth)
{
    struct Macrocheck_Map_Entry_s * re =
        *(struct Macrocheck_Map_Entry_s**)nodep;

    if (which == dwarf_postorder || which == dwarf_endorder) {
        return;
    }
    if (!re->mp_printed) {
        if (lowestfound) {
            if (lowestoff > re->mp_key) {
                lowestoff = re->mp_key;
            }
        } else {
            lowestfound = TRUE;
            lowestoff = re->mp_key;
        }
    }
}

/* Never returns DW_DLV_ERROR */
int
get_next_unprinted_macro_offset(void **tree, Dwarf_Unsigned * off)
{
    lowestfound = FALSE;
    lowestoff = 0;

    /*  This walks the tree to find one entry.
        Which could get slow if the tree has lots of entries. */
    dwarf_twalk(*tree,macro_walk_find_lowest);
    if (!lowestfound) {
        return DW_DLV_NO_ENTRY;
    }
    *off = lowestoff;
    return DW_DLV_OK;
}

void
mark_macro_offset_printed(void **base, Dwarf_Unsigned offset)
{
    struct Macrocheck_Map_Entry_s *re = 0;

    re = macrocheck_map_find(offset,base);
    if (re) {
        re->mp_printed = TRUE;
    }
}


static struct Macrocheck_Map_Entry_s **mac_as_array = 0;
static unsigned mac_as_array_next = 0;
static void
macro_walk_to_array(const void *nodep,const DW_VISIT  which,
    UNUSEDARG const int  depth)
{
    struct Macrocheck_Map_Entry_s * re =
        *(struct Macrocheck_Map_Entry_s**)nodep;

    if (which == dwarf_postorder || which == dwarf_endorder) {
        return;
    }
    mac_as_array[mac_as_array_next] = re;
    mac_as_array_next++;
}

static int
qsort_compare(const void *lin, const void *rin)
{
    const struct Macrocheck_Map_Entry_s *l =
        *(const struct Macrocheck_Map_Entry_s **)lin;
    const struct Macrocheck_Map_Entry_s *r =
        *(const struct Macrocheck_Map_Entry_s **)rin;
    if (l->mp_key < r->mp_key) {
        return -1;
    }
    if (l->mp_key > r->mp_key) {
        return 1;
    }
    if (l->mp_len < r->mp_len) {
        return -1;
    }
    if (l->mp_len > r->mp_len) {
        return 1;
    }
    return 0;
}

int
print_macro_statistics(const char *name,void **tsbase,
    Dwarf_Unsigned section_size,
    UNUSEDARG Dwarf_Error * err)
{
    Dwarf_Unsigned count = 0;
    Dwarf_Unsigned lowest = -1ll;
    Dwarf_Unsigned highest = 0;
    Dwarf_Unsigned lastend = 0;
    Dwarf_Unsigned laststart = 0;
    Dwarf_Unsigned internalgap = 0;
    Dwarf_Unsigned wholegap = 0;
    Dwarf_Unsigned i = 0;

    if(! *tsbase) {
        return DW_DLV_NO_ENTRY;
    }
    count = macro_count_recs(tsbase);
    if (count < 1) {
        return DW_DLV_NO_ENTRY;
    }
    free(mac_as_array);
    mac_as_array = 0;
    mac_as_array_next = 0;
    mac_as_array = (struct Macrocheck_Map_Entry_s **)calloc(count,
        sizeof(struct Macrocheck_Map_Entry_s *));
    if(!mac_as_array) {
#ifdef SELFTEST
        ++failcount;
#endif
        glflags.gf_count_major_errors++;
        printf("\nERROR:  Macro checking %s: "
            "unable to allocate %" DW_PR_DUu "pointers\n",
            name,
            count);
        /*  Return OK so dwarfdump.c won't look for Dwarf_Error */
        return DW_DLV_OK;
    }
    dwarf_twalk(*tsbase,macro_walk_to_array);
    printf("  Macro unit count %s: %" DW_PR_DUu "\n",name,count);
    qsort(mac_as_array,
        count,sizeof(struct Macrocheck_Map_Entry_s *),
        qsort_compare);
    for (i = 0; i < count ; ++i) {
        Dwarf_Unsigned end = 0;
        struct Macrocheck_Map_Entry_s *r = mac_as_array[i];
#if 0
        printf("debugging: i %u off 0x%x len 0x%x printed? %u "
            " ref prim: %u  sec: %u\n",
            (unsigned)i,
            (unsigned)r->mp_key,
            (unsigned)r->mp_len,
            (unsigned)r->mp_printed,
            (unsigned)r->mp_refcount_primary,
            (unsigned)r->mp_refcount_secondary);
#endif
        if (r->mp_key < lowest) {
            lowest = r->mp_key;
        }
        end = r->mp_key + r->mp_len;
        if (end > highest) {
            highest = end;
        }
        if (r->mp_refcount_primary > 1) {
#ifdef SELFTEST
            ++failcount;
#endif
            glflags.gf_count_major_errors++;
            printf("\nERROR: For offset 0x%" DW_PR_XZEROS DW_PR_DUx
                " %" DW_PR_DUu
                " there is a primary reference count of "
                "0x%"  DW_PR_XZEROS DW_PR_DUx
                " %"  DW_PR_DUu "\n",
                r->mp_key,
                r->mp_key,
                r->mp_refcount_primary,
                r->mp_refcount_primary);
        }
        if (r->mp_refcount_primary && r->mp_refcount_secondary) {
#ifdef SELFTEST
            ++failcount;
#endif
            glflags.gf_count_major_errors++;
            printf("\nERROR: For offset 0x%" DW_PR_XZEROS DW_PR_DUx
                " %" DW_PR_DUu
                " there is a nonzero primary count of "
                "0x%"  DW_PR_XZEROS DW_PR_DUx
                " %" DW_PR_DUu
                " with a secondary count of "
                "0x%"  DW_PR_XZEROS DW_PR_DUx
                " %" DW_PR_DUu
                "\n",
                r->mp_key,
                r->mp_key,
                r->mp_refcount_primary,
                r->mp_refcount_primary,
                r->mp_refcount_secondary,
                r->mp_refcount_secondary);
        }
    }
    lastend =
        mac_as_array[0]->mp_key +
        mac_as_array[0]->mp_len;
    laststart = mac_as_array[0]->mp_key;
    printf("  Macro Offsets start at 0x%" DW_PR_XZEROS DW_PR_DUx
        " and end at 0x%" DW_PR_XZEROS DW_PR_DUx "\n",
        lowest, highest);
    for (i = 1; i < count ; ++i) {
        struct Macrocheck_Map_Entry_s *r = mac_as_array[i];
#if 0
        printf("debugging i %u off 0x%x len 0x%x\n",
            (unsigned)i,
            (unsigned)r->mp_key,
            (unsigned)r->mp_len);
#endif
        if (r->mp_key > lastend) {
            internalgap += (r->mp_key - lastend);
        } else if (r->mp_key < lastend) {
            /* crazy overlap */
#ifdef SELFTEST
            ++failcount;
#endif
            glflags.gf_count_major_errors++;
            printf(" ERROR: For offset 0x%" DW_PR_XZEROS DW_PR_DUx
                " %" DW_PR_DUu
                " there is a crazy overlap with the previous end offset of "
                "0x%"  DW_PR_XZEROS DW_PR_DUx
                " %"  DW_PR_DUu
                " (previous start offset of 0x%"  DW_PR_XZEROS DW_PR_DUx ")"
                " %"  DW_PR_DUu
                "\n",
                r->mp_key,
                r->mp_key,
                lastend,
                lastend,
                laststart,
                laststart);
        }
        laststart = r->mp_key;
        lastend   = laststart + r->mp_len;
    }
    /*  wholegap is a) starting offset > 0 and b)
        space after used area before end of section. */
    wholegap = mac_as_array[0]->mp_key + internalgap;
    if (lastend > section_size) {
        /* Something seriously wrong */
#ifdef SELFTEST
        ++failcount;
#endif
        printf(" ERROR: For offset 0x%" DW_PR_XZEROS DW_PR_DUx
            " %" DW_PR_DUu
            " there is an overlap with the end of section "
            "0x%"  DW_PR_XZEROS DW_PR_DUx
            " %" DW_PR_DUu
            "\n",laststart,laststart,
            lastend, lastend);
    } else {
        wholegap += (section_size - lastend);
    }
    if(wholegap) {
        printf("  Macro Offsets internal unused space: "
            "0x%" DW_PR_XZEROS DW_PR_DUx
            "\n",
            internalgap);
        printf("  Macro Offsets total    unused space: "
            "0x%" DW_PR_XZEROS DW_PR_DUx
            "\n",
            wholegap);
    }
    free (mac_as_array);
    mac_as_array = 0;
    mac_as_array_next = 0;
    return DW_DLV_OK;
}

void
clear_macro_statistics(void **tsbase)
{
    if(! *tsbase) {
        return;
    }
    macrocheck_map_destroy(*tsbase);
    *tsbase = 0;
}


#ifdef SELFTEST
int
main()
{
    void * base = 0;
    Dwarf_Unsigned count = 0;
    int basefailcount = 0;
    Dwarf_Error err = 0;

    /* Test 1 */
    add_macro_import(&base,TRUE,200);
    count = macro_count_recs(&base);
    if (count != 1) {
        printf("FAIL: expect count 1, got %" DW_PR_DUu "\n",count);
        ++failcount;
    }
    print_macro_statistics("test1",&base,2000,&err);

    /* Test two */
    add_macro_area_len(&base,200,100);
    add_macro_import(&base,FALSE,350);
    add_macro_area_len(&base,350,100);
    count = macro_count_recs(&base);
    if (count != 2) {
        printf("FAIL: expect count 2, got %" DW_PR_DUu "\n",count);
        ++failcount;
    }
    print_macro_statistics("test 2",&base,2000,&err);
    clear_macro_statistics(&base);

    /* Test three */
    basefailcount = failcount;
    add_macro_import(&base,TRUE,0);
    add_macro_area_len(&base,0,1000);
    add_macro_import(&base,FALSE,2000);
    add_macro_area_len(&base,2000,100);
    mark_macro_offset_printed(&base,2000);
    add_macro_import(&base,FALSE,1000);
    add_macro_area_len(&base,1000,900);
    add_macro_import(&base,FALSE,1000);
    add_macro_area_len(&base,1000,900);
    count = macro_count_recs(&base);
    if (count != 3) {
        printf("FAIL: expect count 3, got %" DW_PR_DUu "\n",count);
        ++failcount;
    }
    printf("\n  Expect an ERROR about overlap with "
        "the end of section\n");
    print_macro_statistics("test 3",&base,2000,&err);
    clear_macro_statistics(&base);
    if ((basefailcount+1) != failcount) {
        printf("FAIL: Found no error in test 3 checking!\n");
        ++failcount;
    } else {
        failcount = basefailcount;
    }

    /* Test Four */
    basefailcount = failcount;
    add_macro_import(&base,TRUE,50);
    add_macro_import(&base,TRUE,50);
    add_macro_area_len(&base,50,50);
    add_macro_import(&base,FALSE,200);
    add_macro_import(&base,FALSE,50);
    add_macro_import(&base,FALSE,60);
    add_macro_area_len(&base,60,10);
    printf( "\n  Expect an ERROR about offset 50 having 2 primaries\n");
    printf( "  and Expect an ERROR about offset 50 having 2\n"
        "  primaries"
        " and a secondary\n");
    printf( "  and Expect an ERROR about crazy overlap 60\n\n");
    print_macro_statistics("test 4",&base,2000,&err);
    clear_macro_statistics(&base);
    if ((basefailcount + 3) != failcount) {
        printf("FAIL: Found wrong errors in test 4 checking!\n");
    } else {
        failcount = basefailcount;
    }
    if (failcount > 0) {
        printf("FAIL macrocheck selftest\n");
        exit(1);
    }
    printf("PASS macrocheck selftest\n");
    return 0;
}
#endif /* SELFTEST */