/*      $OpenBSD: targequiv.c,v 1.11 2024/06/18 02:11:04 millert Exp $ */
/*
 * Copyright (c) 2007-2008 Marc Espie.
 *
 * Extensive code changes for the OpenBSD project.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
 * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/* Compute equivalence tables of targets, helpful for VPATH and parallel
 * make.
 */

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ohash.h>
#include <limits.h>
#include "defines.h"
#include "memory.h"
#include "gnode.h"
#include "lst.h"
#include "suff.h"
#include "dir.h"
#include "targ.h"
#include "targequiv.h"

struct equiv_list {
        GNode *first, *last;
        char name[1];
};

static struct ohash_info equiv_info = {
        offsetof(struct equiv_list, name), NULL, hash_calloc, hash_free,
        element_alloc
};

static void attach_node(GNode *, GNode *);
static void build_equivalence(void);
static void add_to_equiv_list(struct ohash *, GNode *);
static char *names_match(GNode *, GNode *);
static char *names_match_with_dir(const char *, const char *, char *,
    char *,  const char *);
static char *names_match_with_dirs(const char *, const char *, char *,
    char *,  const char *, const char *);
static char *relative_reduce(const char *, const char *);
static char *relative_reduce2(const char *, const char *, const char *);
static char *absolute_reduce(const char *);
static size_t parse_reduce(size_t, const char *);
static void find_siblings(GNode *);

/* These functions build `equivalence lists' of targets with the same
 * basename, as circular lists. They use an intermediate ohash as scaffold,
 * to insert same-basename targets in a simply linked list. Then they make
 * those lists circular, to the exception of lone elements, since they can't
 * alias to anything.
 *
 * This structure is used to simplify alias-lookup to a great extent: two
 * nodes can only alias each other if they're part of the same equivalence
 * set. Most nodes either don't belong to an alias set, or to a very simple
 * alias set, thus removing most possibilities.
 */
static void
add_to_equiv_list(struct ohash *equiv, GNode *gn)
{
        const char *end = NULL;
        struct equiv_list *e;
        unsigned int slot;

        if (!should_have_file(gn))
                return;

        gn->basename = strrchr(gn->name, '/');
        if (gn->basename == NULL)
                gn->basename = gn->name;
        else
                gn->basename++;
        slot = ohash_qlookupi(equiv, gn->basename, &end);
        e = ohash_find(equiv, slot);
        if (e == NULL) {
                e = ohash_create_entry(&equiv_info, gn->basename, &end);
                e->first = NULL;
                e->last = gn;
                ohash_insert(equiv, slot, e);
        }
        gn->next = e->first;
        e->first = gn;
}

static void
build_equivalence(void)
{
        unsigned int i;
        GNode *gn;
        struct equiv_list *e;
        struct ohash equiv;
        struct ohash *t = targets_hash();


        ohash_init(&equiv, 10, &equiv_info);

        for (gn = ohash_first(t, &i); gn != NULL; gn = ohash_next(t, &i))
                add_to_equiv_list(&equiv, gn);

        /* finish making the lists circular */
        for (e = ohash_first(&equiv, &i); e != NULL;
            e = ohash_next(&equiv, &i)) {
                if (e->last != e->first)
                        e->last->next = e->first;
                free(e);
        }
        ohash_delete(&equiv);
}

static const char *curdir, *objdir;
static char *kobjdir;
static size_t objdir_len;

void
Targ_setdirs(const char *c, const char *o)
{
        curdir = c;
        objdir = o;

        objdir_len = strlen(o);
        kobjdir = emalloc(objdir_len+2);
        memcpy(kobjdir, o, objdir_len);
        kobjdir[objdir_len++] = '/';
        kobjdir[objdir_len] = 0;
}


void
kludge_look_harder_for_target(GNode *gn)
{
        GNode *extra, *cgn;
        LstNode ln;

        if (strncmp(gn->name, kobjdir, objdir_len) == 0) {
                extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE);
                if (extra != NULL) {
                        if (Lst_IsEmpty(&gn->commands))
                                Lst_Concat(&gn->commands, &extra->commands);
                        for (ln = Lst_First(&extra->children); ln != NULL;
                            ln = Lst_Adv(ln)) {
                                cgn = Lst_Datum(ln);

                                if (Lst_AddNew(&gn->children, cgn)) {
                                        Lst_AtEnd(&cgn->parents, gn);
                                        gn->children_left++;
                                }
                        }
                }
        }
}

static void
attach_node(GNode *gn, GNode *extra)
{
        /* XXX normally extra->sibling == extra, but this is not
         * always the case yet, so we merge the two lists
         */
        GNode *tmp;

        tmp = gn->sibling;
        gn->sibling = extra->sibling;
        extra->sibling = tmp;
}

static char *buffer = NULL;
static size_t bufsize = PATH_MAX;

static size_t
parse_reduce(size_t i, const char *src)
{
        while (src[0] != 0) {
                while (src[0] == '/')
                        src++;
                /* special cases */
                if (src[0] == '.') {
                        if (src[1] == '/') {
                                src += 2;
                                continue;
                        }
                        if (src[1] == '.' && src[2] == '/') {
                                src += 3;
                                i--;
                                while (i > 0 && buffer[i-1] != '/')
                                        i--;
                                if (i == 0)
                                        i = 1;
                                continue;
                        }
                }
                while (src[0] != '/' && src[0] != 0) {
                        if (i > bufsize - 2) {
                                bufsize *= 2;
                                buffer = erealloc(buffer, bufsize);
                        }
                        buffer[i++] = *src++;
                }
                if (src[0] == '/') 
                        buffer[i++] = *src++;
        }
        buffer[i++] = 0;
        return i;
}

static char *
absolute_reduce(const char *src)
{
        size_t i = 0;

        if (buffer == NULL)
                buffer = emalloc(bufsize);

        buffer[i++] = '/';
        i = parse_reduce(i, src);
        return estrdup(buffer);
}

static char *
relative_reduce(const char *dir, const char *src)
{
        size_t i = 0;

        if (buffer == NULL)
                buffer = emalloc(bufsize);

        buffer[i++] = '/';
        i = parse_reduce(i, dir);
        i--;

        if (buffer[i-1] != '/')
                buffer[i++] = '/';
        i = parse_reduce(i, src);
        return estrdup(buffer);
}

static char *
relative_reduce2(const char *dir1, const char *dir2, const char *src)
{
        size_t i = 0;

        if (buffer == NULL)
                buffer = emalloc(bufsize);

        buffer[i++] = '/';
        i = parse_reduce(i, dir1);
        i--;
        if (buffer[i-1] != '/')
                buffer[i++] = '/';

        i = parse_reduce(i, dir2);
        i--;
        if (buffer[i-1] != '/')
                buffer[i++] = '/';

        i = parse_reduce(i, src);
        return estrdup(buffer);
}

static char *
names_match_with_dir(const char *a, const char *b, char *ra,
    char *rb,  const char *dir)
{
        bool r;
        bool free_a, free_b;

        if (ra == NULL) {
                ra = relative_reduce(dir, a);
                free_a = true;
        } else {
                free_a = false;
        }

        if (rb == NULL) {
                rb = relative_reduce(dir, b);
                free_b = true;
        } else {
                free_b = false;
        }
        r = strcmp(ra, rb) == 0;
        if (free_a)
                free(ra);
        if (r)
                return rb;
        else {
                if (free_b)
                        free(rb);
                return NULL;
        }
}

static char *
names_match_with_dirs(const char *a, const char *b, char *ra,
    char *rb,  const char *dir1, const char *dir2)
{
        bool r;
        bool free_a, free_b;

        if (ra == NULL) {
                ra = relative_reduce2(dir1, dir2, a);
                free_a = true;
        } else {
                free_a = false;
        }

        if (rb == NULL) {
                rb = relative_reduce2(dir1, dir2, b);
                free_b = true;
        } else {
                free_b = false;
        }
        r = strcmp(ra, rb) == 0;
        if (free_a)
                free(ra);
        if (r)
                return rb;
        else {
                if (free_b)
                        free(rb);
                return NULL;
        }
}

static char *
names_match(GNode *a, GNode *b)
{
        char *ra = NULL , *rb = NULL;
        char *r;

        if (a->name[0] == '/')
                ra = absolute_reduce(a->name);
        if (b->name[0] == '/')
                rb = absolute_reduce(b->name);
        if (ra && rb) {
                if (strcmp(ra, rb) == 0)
                        r = rb;
                else
                        r = NULL;
        } else {
                r = names_match_with_dir(a->name, b->name, ra, rb, objdir);
                if (!r)
                        r = names_match_with_dir(a->name, b->name, ra, rb,
                            curdir);
                if (!r) {
                        /* b has necessarily the same one */
                        Lst l = find_suffix_path(a);
                        LstNode ln;

                        for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
                                const char *p = PathEntry_name(Lst_Datum(ln));
                                if (p[0] == '/') {
                                        r = names_match_with_dir(a->name,
                                            b->name, ra, rb, p);
                                        if (r)
                                                break;
                                } else {
                                        r = names_match_with_dirs(a->name,
                                            b->name, ra, rb, p, objdir);
                                        if (r)
                                                break;
                                        r = names_match_with_dirs(a->name,
                                            b->name, ra, rb, p, curdir);
                                        if (r)
                                                break;
                                }
                        }
                }
        }
        free(ra);
        if (r != rb)
                free(rb);
        return r;
}

static void
find_siblings(GNode *gn)
{
        GNode *gn2;
        char *fullpath;

        /* not part of an equivalence class: can't alias */
        if (gn->next == NULL)
                return;
        /* already resolved, actually */
        if (gn->sibling != gn)
                return;
        if (DEBUG(NAME_MATCHING))
                fprintf(stderr, "Matching for %s:", gn->name);
        /* look through the aliases */
        for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) {
                fullpath = names_match(gn, gn2);
                if (fullpath) {
                        attach_node(gn, gn2);
                } else {
                        if (DEBUG(NAME_MATCHING))
                                fputc('!', stderr);
                }
                if (DEBUG(NAME_MATCHING))
                        fprintf(stderr, "%s ", gn2->name);
        }
        if (DEBUG(NAME_MATCHING))
                fputc('\n', stderr);
}

void
look_harder_for_target(GNode *gn)
{
        static bool equiv_was_built = false;

        if (!equiv_was_built) {
                build_equivalence();
                equiv_was_built = true;
        }

        if (gn->type & (OP_RESOLVED | OP_PHONY))
                return;
        gn->type |= OP_RESOLVED;
        find_siblings(gn);
}

bool
is_sibling(GNode *gn, GNode *gn2)
{
        GNode *sibling;

        sibling = gn;
        do {
                if (sibling == gn2)
                        return true;
                sibling = sibling->sibling;
        } while (sibling != gn);

        return false;
}