/*
 * Copyright (c) 2019 The DragonFly Project.  All rights reserved.
 *
 * This code is derived from software contributed to The DragonFly Project
 * by Matthew Dillon <dillon@backplane.com>
 *
 * This code uses concepts and configuration based on 'synth', by
 * John R. Marino <draco@marino.st>, which was written in ada.
 *
 * 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.
 * 3. Neither the name of The DragonFly Project nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific, prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS 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
 * COPYRIGHT HOLDERS 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.
 */
/*
 * Figure out what would have to be built [N]ew, [R]ebuild, [U]pgrade
 * but do not perform any action.
 */
#include "dsynth.h"

static int status_find_leaves(pkg_t *parent, pkg_t *pkg, pkg_t ***build_tailp,
			int *app, int *hasworkp, int level, int first);
static void status_clear_trav(pkg_t *pkg);
static void startstatus(pkg_t **build_listp, pkg_t ***build_tailp);

void
DoStatus(pkg_t *pkgs)
{
	pkg_t *build_list = NULL;
	pkg_t **build_tail = &build_list;
	pkg_t *scan;
	int haswork = 1;
	int first = 1;

	/*
	 * Count up all the packages, do not include dummy packages.
	 */
	for (scan = pkgs; scan; scan = scan->bnext) {
		if ((scan->flags & PKGF_DUMMY) == 0)
			++BuildTotal;
	}

	/*
	 * Nominal bulk build sequence
	 */
	while (haswork) {
		haswork = 0;
		fflush(stdout);
		for (scan = pkgs; scan; scan = scan->bnext) {
			ddprintf(0, "SCANLEAVES %08x %s\n",
				 scan->flags, scan->portdir);
			scan->flags |= PKGF_BUILDLOOP;
			/*
			 * NOTE: We must still find dependencies if PACKAGED
			 *	 to fill in the gaps, as some of them may
			 *	 need to be rebuilt.
			 */
			if (scan->flags & (PKGF_SUCCESS | PKGF_FAILURE |
					   PKGF_ERROR | PKGF_NOBUILD)) {
#if 0
				ddprintf(0, "%s: already built\n",
					 scan->portdir);
#endif
			} else {
				int ap = 0;
				status_find_leaves(NULL, scan, &build_tail,
						  &ap, &haswork, 0, first);
				ddprintf(0, "TOPLEVEL %s %08x\n",
					 scan->portdir, ap);
			}
			scan->flags &= ~PKGF_BUILDLOOP;
			status_clear_trav(scan);
		}
		first = 0;
		fflush(stdout);
		if (haswork == 0)
			break;
		startstatus(&build_list, &build_tail);
	}
	printf("Total packages that would be built: %d/%d\n",
	       BuildSuccessCount, BuildTotal);
}

/*
 * Traverse the packages (pkg) depends on recursively until we find
 * a leaf to build or report as unbuildable.  Calculates and assigns a
 * dependency count.  Returns all parallel-buildable packages.
 *
 * (pkg) itself is only added to the list if it is immediately buildable.
 */
static
int
status_find_leaves(pkg_t *parent, pkg_t *pkg, pkg_t ***build_tailp,
		  int *app, int *hasworkp, int level, int first)
{
	pkglink_t *link;
	pkg_t *scan;
	int idep_count = 0;
	int apsub;

	/*
	 * Already on build list, possibly in-progress, tell caller that
	 * it is not ready.
	 */
	ddprintf(level, "sbuild_find_leaves %d %s %08x {\n",
		 level, pkg->portdir, pkg->flags);
	if (pkg->flags & PKGF_BUILDLIST) {
		ddprintf(level, "} (already on build list)\n");
		*app |= PKGF_NOTREADY;
		return (pkg->idep_count);
	}

	/*
	 * Check dependencies
	 */
	++level;
	PKGLIST_FOREACH(link, &pkg->idepon_list) {
		scan = link->pkg;

		if (scan == NULL)
			continue;
		ddprintf(level, "check %s %08x\t", scan->portdir, scan->flags);

		/*
		 * When accounting for a successful build, just bump
		 * idep_count by one.  scan->idep_count will heavily
		 * overlap packages that we count down multiple branches.
		 *
		 * We must still recurse through PACKAGED packages as
		 * some of their dependencies might be missing.
		 */
		if (scan->flags & PKGF_SUCCESS) {
			ddprintf(0, "SUCCESS - OK\n");
			++idep_count;
			continue;
		}
		if (scan->flags & PKGF_ERROR) {
			ddprintf(0, "ERROR - OK (propagate failure upward)\n");
			*app |= PKGF_NOBUILD_S;
			continue;
		}
		if (scan->flags & PKGF_NOBUILD) {
			ddprintf(0, "NOBUILD - OK "
				    "(propagate failure upward)\n");
			*app |= PKGF_NOBUILD_S;
			continue;
		}

		/*
		 * If already on build-list this dependency is not ready.
		 */
		if (scan->flags & PKGF_BUILDLIST) {
			ddprintf(0, " [BUILDLIST]");
			*app |= PKGF_NOTREADY;
		}

		/*
		 * If not packaged this dependency is not ready for
		 * the caller.
		 */
		if ((scan->flags & PKGF_PACKAGED) == 0) {
			ddprintf(0, " [NOT_PACKAGED]");
			*app |= PKGF_NOTREADY;
		}

		/*
		 * Reduce search complexity, if we have already processed
		 * scan in the traversal it will either already be on the
		 * build list or it will not be buildable.  Either way
		 * the parent is not buildable.
		 */
		if (scan->flags & PKGF_BUILDTRAV) {
			ddprintf(0, " [BUILDTRAV]\n");
			*app |= PKGF_NOTREADY;
			continue;
		}

		/*
		 * Assert on dependency loop
		 */
		++idep_count;
		if (scan->flags & PKGF_BUILDLOOP) {
			dfatal("pkg dependency loop %s -> %s",
				parent->portdir, scan->portdir);
		}
		scan->flags |= PKGF_BUILDLOOP;
		apsub = 0;
		ddprintf(0, " SUBRECURSION {\n");
		idep_count += status_find_leaves(pkg, scan, build_tailp,
						&apsub, hasworkp,
						level + 1, first);
		scan->flags &= ~PKGF_BUILDLOOP;
		*app |= apsub;
		if (apsub & PKGF_NOBUILD) {
			ddprintf(level, "} (sub-nobuild)\n");
		} else if (apsub & PKGF_ERROR) {
			ddprintf(level, "} (sub-error)\n");
		} else if (apsub & PKGF_NOTREADY) {
			ddprintf(level, "} (sub-notready)\n");
		} else {
			ddprintf(level, "} (sub-ok)\n");
		}
	}
	--level;
	pkg->idep_count = idep_count;
	pkg->flags |= PKGF_BUILDTRAV;

	/*
	 * Incorporate scan results into pkg state.
	 */
	if ((pkg->flags & PKGF_NOBUILD) == 0 && (*app & PKGF_NOBUILD)) {
		*hasworkp = 1;
	} else if ((pkg->flags & PKGF_ERROR) == 0 && (*app & PKGF_ERROR)) {
		*hasworkp = 1;
	}
	pkg->flags |= *app & ~PKGF_NOTREADY;

	/*
	 * Clear PACKAGED bit if sub-dependencies aren't clean
	 */
	if ((pkg->flags & PKGF_PACKAGED) &&
	    (pkg->flags & (PKGF_NOTREADY|PKGF_ERROR|PKGF_NOBUILD))) {
		pkg->flags &= ~PKGF_PACKAGED;
		ddassert(pkg->pkgfile);
		*hasworkp = 1;
	}

	/*
	 * Handle propagated flags
	 */
	if (pkg->flags & PKGF_ERROR) {
		ddprintf(level, "} (ERROR - %s)\n", pkg->portdir);
	} else if (pkg->flags & PKGF_NOBUILD) {
		ddprintf(level, "} (SKIPPED - %s)\n", pkg->portdir);
	} else if (*app & PKGF_NOTREADY) {
		/*
		 * We don't set PKGF_NOTREADY in the pkg, it is strictly
		 * a transient flag propagated via build_find_leaves().
		 *
		 * Just don't add the package to the list.
		 */
		;
	} else if (pkg->flags & PKGF_SUCCESS) {
		ddprintf(level, "} (SUCCESS - %s)\n", pkg->portdir);
	} else if (pkg->flags & PKGF_DUMMY) {
		/*
		 * Just mark dummy packages as successful when all of their
		 * sub-depends (flavors) complete successfully.  Note that
		 * dummy packages are not counted in the total, so do not
		 * decrement BuildTotal.
		 */
		ddprintf(level, "} (DUMMY/META - SUCCESS)\n");
		pkg->flags |= PKGF_SUCCESS;
		*hasworkp = 1;
		if (first) {
			dlog(DLOG_ALL | DLOG_FILTER,
			     "[XXX] %s META-ALREADY-BUILT\n",
			     pkg->portdir);
		} else {
			dlog(DLOG_SUCC | DLOG_FILTER,
			     "[XXX] %s meta-node complete\n",
			     pkg->portdir);
		}
	} else if (pkg->flags & PKGF_PACKAGED) {
		/*
		 * We can just mark the pkg successful.  If this is
		 * the first pass, we count this as an initial pruning
		 * pass and reduce BuildTotal.
		 */
		ddprintf(level, "} (PACKAGED - SUCCESS)\n");
		pkg->flags |= PKGF_SUCCESS;
		*hasworkp = 1;
		if (first) {
			dlog(DLOG_ALL | DLOG_FILTER,
			    "[XXX] %s ALREADY-BUILT\n",
			     pkg->portdir);
			--BuildTotal;
		}
	} else {
		/*
		 * All dependencies are successful, queue new work
		 * and indicate not-ready to the parent (since our
		 * package has to be built).
		 */
		*hasworkp = 1;
		ddprintf(level, "} (ADDLIST - %s)\n", pkg->portdir);
		pkg->flags |= PKGF_BUILDLIST;
		**build_tailp = pkg;
		*build_tailp = &pkg->build_next;
		*app |= PKGF_NOTREADY;
	}

	return idep_count;
}

static
void
status_clear_trav(pkg_t *pkg)
{
	pkglink_t *link;
	pkg_t *scan;

	pkg->flags &= ~PKGF_BUILDTRAV;
	PKGLIST_FOREACH(link, &pkg->idepon_list) {
		scan = link->pkg;
		if (scan && (scan->flags & PKGF_BUILDTRAV))
			status_clear_trav(scan);
	}
}

/*
 * This is a fake startbuild() which just marks the build list as built,
 * allowing us to resolve the build tree.
 */
static
void
startstatus(pkg_t **build_listp, pkg_t ***build_tailp)
{
	pkg_t *pkg;

	/*
	 * Nothing to do
	 */
	if (*build_listp == NULL)
		return;

	/*
	 * Sort
	 */
	for (pkg = *build_listp; pkg; pkg = pkg->build_next) {
		if ((pkg->flags & (PKGF_SUCCESS | PKGF_FAILURE |
				   PKGF_ERROR | PKGF_NOBUILD |
				   PKGF_RUNNING)) == 0) {
			pkg->flags |= PKGF_SUCCESS;
			++BuildSuccessCount;
			++BuildCount;
			pkg->flags &= ~PKGF_BUILDLIST;
			printf("  N => %s\n", pkg->portdir);
			/* XXX [R]ebuild and [U]pgrade */
		}

	}
	*build_listp = NULL;
	*build_tailp = build_listp;
}