# Copyright (C) 2009, 2010  Roman Zimbelmann <romanz@lavabit.com>
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

from collections import deque

def flatten(lst):
	"""
	Flatten an iterable.

	All contained tuples, lists, deques and sets are replaced by their
	elements and flattened as well.
	"""
	for elem in lst:
		if isinstance(elem, (tuple, list, set, deque)):
			for subelem in flatten(elem):
				yield subelem
		else:
			yield elem

def unique(iterable):
	"""
	Return an iterable of the same type which contains unique items.

	This function assumes that:
	type(iterable)(list(iterable)) == iterable
	which is true for tuples, lists and deques (but not for strings)
pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */
#!/bin/sh
# Experimental alternative to build2 that can run steps in parallel if their
# dependencies are met. Caveats:
#
#   1. We rely on the OS to schedule steps, so thousands of independent tasks
#      will likely be counter-productive.
#   2. Can run out of virtual memory if you spawn too many say $CC processes.
#   3. Compilation errors can cause the script to hang. We tag the most common
#      suspects with '|| quit', but can't eliminate the possibility entirely.
#   4. Ugly as heck! This version really benefits from comparisons with its
#      'upstream', build2. And even then, diff gets confused.
#   5. There's a mechanical difficulty: we use mktemp to reliably create
#      temporary filenames, which has the side effect of also creating the
#      files. So zero-size files are considered equivalent to non-existent
#      files. When some commands have trouble with this (e.g. ar) we need to
#      delete the empty file, which can expose us to a race condition wrt
#      mktemp.

set -e  # stop immediately on error

# Some environment variables that can be passed in. For example, to turn off
# optimization:
#   $ CFLAGS=-g ./build4
test "$CXX" || export CXX=c++
test "$CC" || export CC=cc
test "$CFLAGS" || export CFLAGS="-g -O2"
export CFLAGS="$CFLAGS -Wall -Wextra -ftrapv -fno-strict-aliasing"
export CXXFLAGS="-std=c++98 $CFLAGS"  # CI has an ancient version; don't expect recent dialects

# Outline:
# [0-9]*.cc -> mu.cc -> .build/*.cc -> .build/*.o -> .build/mu_bin
# (layers)   |        |              |             |
#          tangle  cleave          $CXX          $CXX

# can also be called with a layer to only build until
#   $ ./build4 --until 050
UNTIL_LAYER=${2:-zzz}

# there's two mechanisms for fast builds here:
# - if a command is quick to run, always run it but update the result only on any change
# - otherwise run it only if the output is 'older_than' the inputs
#
# avoid combining both mechanisms for a single file
# otherwise you'll see spurious messages about files being updated
# risk: a file may unnecessarily update without changes, causing unnecessary work downstream

# return 1 if $1 is older than _any_ of the remaining args
older_than() {
  local target=$1
  shift
  if [ ! -s $target ]
  then
#?     echo "$target has size zero"
#?     echo "updating $target" >&2
    return 0  # success
  fi
  local f
  for f in $*
  do
    if [ $f -nt $target ]
    then
#?       echo "updating $target" >&2
      return 0  # success
    fi
  done
  return 1  # failure
}

# redirect to $1, unless it's already identical
update() {
  if [ ! -e $1 ]
  then
    cat > $1
  else
    cat > $1.tmp
    diff -q $1 $1.tmp >/dev/null  &&  rm $1.tmp  ||  mv $1.tmp $1
  fi
}

update_cp() {
  if [ ! -e $2/$1 ]
  then
    cp $1 $2
  elif [ $1 -nt $2/$1 ]
  then
    cp $1 $2
  fi
}

noisy_cd() {
  cd $1
  echo "-- `pwd`" >&2
}

mv_if_exists() {
  test -e $1  &&  mv $1 $2
  return 0
}

# wait for all the given filenames to exist
# exit immediately if a special file called '.quit' exists
QUITFILE=`pwd`/.quit
rm -f $QUITFILE
wait_for_all() {
  # could use inotify on Linux
  while ! all_exist "$@"
  do
#?     echo waiting: $*
    test -e $QUITFILE  &&  return 1  # some step had an error; stop all waiting steps using errexit
    sleep 1
  done
  return 0
}
quit() {
  touch $QUITFILE
  exit 1
}

all_exist() {
  for f in "$@"
  do
    test -e $f  ||  return 1
  done
  return 0
}

TMP=`mktemp`
mv_if_exists ../../tools/enumerate $TMP
(
  wait_for_all ../../tools/enumerate.cc
  older_than $TMP ../../tools/enumerate.cc && {
    echo "building enumerate"
    $CXX $CXXFLAGS ../../tools/enumerate.cc -o $TMP  ||  quit
    echo "done building enumerate"
  }
  mv $TMP ../../tools/enumerate
) &

TMP=`mktemp`
mv_if_exists ../../tools/tangle $TMP
(
  wait_for_all ../../tools/tangle.cc
  older_than $TMP ../../tools/tangle.cc && {
    echo "building tangle"
    cd ../../tools
      # auto-generate various lists (ending in '_list' by convention) {
      # list of function declarations, so I can define them in any order
      grep -h "^[^ #].*) {" tangle.cc  |sed 's/ {.*/;/'  |update tangle.function_list
      # list of tests to run
      grep -h "^[[:space:]]*void test_" tangle.cc  |sed 's/^\s*void \(.*\)() {$/\1,/'  |update tangle.test_list
      grep -h "^\s*void test_" tangle.cc  |sed 's/^\s*void \(.*\)() {.*/"\1",/'  |update tangle.test_name_list
      # }
      # Now that we have all the _lists, compile 'tangle'
      $CXX $CXXFLAGS tangle.cc -o $TMP  ||  quit
      $TMP test
    cd ../archive/1.vm
    echo "done building tangle"
  }
  mv $TMP ../../tools/tangle
) &

wait_for_all ../../tools/enumerate
echo "enumerating layers"
LAYERS=$(../../tools/enumerate --until $UNTIL_LAYER  |grep '\.cc$')
echo "done enumerating layers"

TMP=`mktemp`
mv_if_exists mu.cc $TMP
(
  wait_for_all $LAYERS ../../tools/enumerate ../../tools/tangle
  older_than $TMP $LAYERS ../../tools/enumerate ../../tools/tangle && {
    echo "running tangle"
    # no update here; rely on 'update' calls downstream
    ../../tools/tangle $LAYERS >$TMP  ||  quit
    echo "done running tangle"
  }
  mv $TMP mu.cc
) &

TMP=`mktemp`
mv_if_exists cleave/cleave $TMP
(
  wait_for_all cleave/cleave.cc
  older_than $TMP cleave/cleave.cc && {
    echo "building cleave"
    $CXX $CXXFLAGS cleave/cleave.cc -o $TMP  ||  quit
    rm -rf .build
    echo "done building cleave"
  }
  mv $TMP cleave/cleave
) &

wait_for_all mu.cc cleave/cleave  # cleave/cleave just for the .build cleanup
mkdir -p .build
# auto-generate function declarations, so I can define them in any order
# functions start out unindented, have all args on the same line, and end in ') {'
#
#                                      \/ ignore struct/class methods
grep -h "^[^[:space:]#].*) {$" mu.cc  |grep -v ":.*("  |sed 's/ {.*/;/'  |update .build/function_list
# auto-generate list of tests to run
grep -h "^\s*void test_" mu.cc  |sed 's/^\s*void \(.*\)() {.*/\1,/'  |update .build/test_list
grep -h "^\s*void test_" mu.cc  |sed 's/^\s*void \(.*\)() {.*/"\1",/'  |update .build/test_name_list
mkdir -p .build/termbox
update_cp termbox/termbox.h .build/termbox

TMP=`mktemp`
mv_if_exists mu_bin $TMP
(
  wait_for_all mu.cc cleave/cleave termbox/*.c termbox/*.h termbox/*.inl
  older_than $TMP mu.cc *_list cleave/cleave termbox/* && {
    echo "building mu_bin"
    cleave/cleave mu.cc .build  ||  quit
    cd .build
      # create the list of global variable declarations from the corresponding definitions
      grep ';' global_definitions_list  |sed 's/[=(].*/;/'  |sed 's/^[^\/# ]/extern &/'  |sed 's/^extern extern /extern /'  |update global_declarations_list
      for f in mu_*.cc
      do
        OBJ=`echo $f |sed 's/\.cc$/.o/'`
        TMP=`mktemp`
        mv_if_exists $OBJ $TMP
        (
          older_than $TMP $f header global_declarations_list function_list test_list && {
            echo "building $OBJ"
            $CXX $CXXFLAGS -c $f -o $TMP  ||  quit
            echo "done building $OBJ"
          }
          mv $TMP $OBJ
        ) &
      done
    cd ../termbox
      TMP=`mktemp`
      mv_if_exists utf8.o $TMP
      (
        older_than $TMP utf8.c && {
          echo "building termbox/utf8.o"
          $CC $CFLAGS -c utf8.c -o $TMP  ||  quit
          echo "done building termbox/utf8.o"
        }
        mv $TMP utf8.o
      ) &
      TMP=`mktemp`
      mv_if_exists termbox.o $TMP
      (
        older_than $TMP termbox.c termbox.h input.inl output.inl bytebuffer.inl && {
          echo "building termbox/termbox.o"
          $CC $CFLAGS -c termbox.c -o $TMP  ||  quit
          echo "done building termbox/termbox.o"
        }
        mv $TMP termbox.o
      ) &
      TMP=`mktemp`
      mv_if_exists libtermbox.a $TMP
      (
        wait_for_all termbox.o utf8.o
        older_than $TMP termbox.o utf8.o && {
          echo "building termbox/libtermbox.a"
          rm $TMP;  ar rcs $TMP termbox.o utf8.o  ||  quit  # race condition; later mktemp may end up reusing this file
          echo "done building termbox/libtermbox.a"
        }
        mv $TMP libtermbox.a
      ) &
    cd ..
    MU_OBJS=`echo .build/mu_*.cc |sed 's/\.cc/.o/g'`
    echo wait_for_all $MU_OBJS termbox/libtermbox.a
    wait_for_all $MU_OBJS termbox/libtermbox.a
    echo "building .build/mu_bin"
    $CXX $CXXFLAGS $MU_OBJS termbox/libtermbox.a -o $TMP  ||  quit
    echo "done building .build/mu_bin"
    echo "done building mu_bin"
  }
  mv $TMP mu_bin
) &

## [0-9]*.mu -> core.mu

wait_for_all ../../tools/enumerate
echo "building core.mu"
MU_LAYERS=$(../../tools/enumerate --until $UNTIL_LAYER  |grep '\.mu$') || exit 0  # ok if no .mu files
cat $MU_LAYERS  |update core.mu
echo "done building core.mu"

wait_for_all mu_bin
exit 0

# scenarios considered:
#   0 status when nothing needs updating
#   only a single layer is recompiled when changing a C++ function
#   stop immediately after any failure