David Gibson [Wed, 23 Nov 2016 12:12:59 +0000 (23:12 +1100)]
.travis.yml: Enable C99 mode for older gcc versions
Currently Travis builds fail on the edit_distance module, because that
module uses C99 extensions, which aren't enabled by default on the
Ubuntu Precise compiler version. Force it to allow these, by adding the
-std=gnu99 option to the compiler.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Sat, 19 Nov 2016 04:19:25 +0000 (21:19 -0700)]
edit_distance: calculate edit distance between strings
This commit creates the edit_distance module for calculating various
edit distance measures. The edit distance quantifies the similarity
between two strings based on the number of modifications necessary to
turn one string into the other. There are several edit distance
measures which differ in the operations which are permitted and the
cost (aka weight) of the operations. This module provides functions
for calculating the Longest Common Subsequence (LCS), Levenshtein, and
Damerau-Levenshtein (restricted and unrestricted) distances. Weighted
versions of these functions can be created by defining cost functions
as preprocessor macros when compiling this module. Distances over
other array types (e.g. wide strings, integers, structs) can be
accomplished by defining the element type and equality test macros.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Tue, 22 Nov 2016 22:50:48 +0000 (09:50 +1100)]
Makefile: Remove unused test targets
The Makefile provides for "fast" and "full" variants of make check.
However, nothing seems to use or implement the "full" variant at all.
Further, the %.check and %.fastcheck targets are not actually used, with
other targets instead using the actual .ok tag file as the target.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 21 Nov 2016 14:05:37 +0000 (01:05 +1100)]
cppmagic: Tweak testcase to work on older clang versions
clang version 3.4, for whatever reason, expands a few of the testcases
in cppmagic with slightly different whitespace from what we expect. Since
this was changed in later clang versions, it was probably a compiler bug,
but it turns out an extra space in the testcase can make it pass on clang
3.4 as well. This means we finally have clang builds working in Travis.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 21 Nov 2016 13:52:53 +0000 (00:52 +1100)]
time: Change TIME_HAVE_MONOTONIC to be 0/1 rather than defined/undefined
Generally, ccan config variables are always defined as either 0 or 1 and
are tested with #if. That's instead of being being either defined or
undefined and tested with #ifdef.
TIME_HAVE_MONOTONIC breaks that convention. This can cause warnings in
ccan/timer which uses it assuming the 0/1 convention. Change it to remove
that warning.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Mon, 21 Nov 2016 12:35:22 +0000 (23:35 +1100)]
.travis.yml: Remove external libraries
The new makefile excludes all modules with external library dependencies
from the usual make check, meaning the libraries are not needed for the
Travis build.
Although it would be nice to include these modules, there are a bunch of
problems with sorting out a correct environment for them. For now, just
leave them out.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 2 Nov 2016 22:35:31 +0000 (09:35 +1100)]
Clearer output from make check in Travis
This removes the parallel make (-j) option when running make check under
Travis CI. This will slow down the build somewhat, but makes it easier to
match errors to the modules which caused them.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 2 Nov 2016 22:34:23 +0000 (09:34 +1100)]
ccanlint: Alter meaning of --summary option
--summary (used by make check) causes ccanlint to only ever print a
one-line summary of the results. When one of the tests fails, this isn't
very useful, because it doesn't say why it failed, or even which test
failed. This is particularly frustrating for failures in Travis CI builds
where it's not always straightforward to reproduce a similar enough build
environment to check the failure manually for a particular module.
--summary does have one purpose which is vital for make check, though: it
suppresses any attempt to interactively correct / improve the module
printing only results.
This changes --summary to only have the second effect, not the first. This
won't change the output in the case of passing modules, but will give more
useful information in the case of failing modules.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Thu, 3 Nov 2016 10:49:55 +0000 (21:49 +1100)]
aga,agar: Negative weight cycle testcase
Adds a new test graph which includes a negative weight cycle. This means
that shortest paths are not well defined, and both Dijkstra's algorithm and
the Bellman-Ford algorithm (which can handle some negative edge weights)
will fail.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 11 Jun 2016 08:30:08 +0000 (18:30 +1000)]
aga,agar: The Bellman-Ford algorithm
This adds the Bellman-Ford single-source shortest path algorithm to
the aga and agar modules. The Bellman-Ford algorithm is (usually)
slower than Dijkstra's algorithm, but unlike Dijkstra's is able to
cope with negative edge costs, unless they form a negative cost cycle.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Sat, 11 Jun 2016 03:10:58 +0000 (13:10 +1000)]
aga,agar: Rename aga_dijkstra_all_paths()
aga_dijkstra_all_paths() runs Dijkstra's algorithm to completion (as
opposed to aga_dijkstra_path(), which operates lazily). In effect this
computes the shortest path to all (reachable) nodes from the start node.
So, in this context the name makes sense. But for an analogous function
for future algorithms (e.g. Bellman-Ford), the name doesn't make sense.
So, in the interests of consistency with those future extensions, change
the name of this to aga_dijkstra_complete().
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
David Gibson [Wed, 2 Nov 2016 06:00:00 +0000 (17:00 +1100)]
.travis.yml: Correct additional packages list
The list of additional packages in our .travis.yml (mostly libraries needed
for specific modules) was incorrectly formatted. So travis was attempting
to install the "libjudy-dev libvorbis-dev libportaudio-dev libtalloc-dev"
packagde (spaces included) which obviously didn't work.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Rusty Russell [Mon, 31 Oct 2016 00:45:33 +0000 (11:15 +1030)]
timer: change to use time_mono (api break!)
Remove timer_add() in favor of explicit timer_addrel and timer_addmono.
Someone hit a real-life case where time went backwards, and we asserted.
The correct fix is to use time_mono() where available, but as all known
users actually want a relative timeout, have a helper for that case.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Tue, 25 Oct 2016 04:46:07 +0000 (15:16 +1030)]
io: fix maybe-uninitialized warning in test (-O2)
/home/rusty/devel/cvs/ccan/ccan/io/test/run-01-start-finish.c: In function ‘main’:
/home/rusty/devel/cvs/ccan/ccan/io/test/run-01-start-finish.c:89:7: warning: ‘addrinfo’ may be used uninitialized in this function [-Wmaybe-uninitialized]
if (connect(fd, addrinfo->ai_addr, addrinfo->ai_addrlen) != 0)
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Tue, 25 Oct 2016 04:45:33 +0000 (15:15 +1030)]
foreach: fixed maybe uninitialized warning in test (-O2)
/home/rusty/devel/cvs/ccan/ccan/tap/tap.h:57:59: warning: ‘max_iters’ may be used uninitialized in this function [-Wmaybe-uninitialized]
_gen_result(1, __func__, __FILE__, __LINE__, "%s", #e) : \
^
/home/rusty/devel/cvs/ccan/ccan/foreach/test/run-nested.c:47:17: note: ‘max_iters’ was declared here
int i, j, sum, max_iters;
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Tue, 25 Oct 2016 04:44:33 +0000 (15:14 +1030)]
err: fix warn-unused-result warning in test (-O2)
/home/rusty/devel/cvs/ccan/ccan/err/test/run.c:124:2: warning: ignoring return value of ‘pipe’, declared with attribute warn_unused_result [-Wunused-result]
pipe(pfd);
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Rusty Russell [Tue, 25 Oct 2016 04:07:00 +0000 (14:37 +1030)]
cdump: fix uninitialized warning with optimization
/home/rusty/devel/cvs/ccan/ccan/cdump/cdump.c: In function ‘get_type’:
/home/rusty/devel/cvs/ccan/ccan/strmap/strmap.h:88:39: warning: ‘m’ may be used uninitialized in this function [-Wmaybe-uninitialized]
tcon_cast((map), canary, strmap_get_(&(map)->raw, (member)))
^
/home/rusty/devel/cvs/ccan/ccan/cdump/cdump.c:216:20: note: ‘m’ was declared here
cdump_map_t *m;
^
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:48 +0000 (18:44 -0600)]
Add appveyor.yml
This file defines the AppVeyor CI (appveyor.com) settings.
It builds using make+bash under MSYS2 so that the current build system
can be used with minimal changes. It currently only builds configurator
and generates config.h.
The build and test commands for more thorough testing are left as
comments in appveyor.yml so interested parties can use them as a
starting point for future work.
Note that several compiler errors not related to configurator are
printed due to make attempting to generate and include test-depends.
Although Windows-specific code could be added to Makefile to avoid
these, it seemed unwarranted if the compile errors may be fixed soon.
Changes since v2:
- Add reference to AppVeyor results for canonical repo and basic
instructions to setup AppVeyor for forks.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:47 +0000 (18:44 -0600)]
Makefile: Define CFLAGS_FORCE_C_SOURCE macro
This macro holds the C compiler flag(s) to force input files to be
recognized as C sources regardless of extension. It is defined to allow
overriding on the make command line.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:46 +0000 (18:44 -0600)]
configurator: DEFAULT_{COMPILER, FLAGS} for MSVC
When compiling with Visual Studio, use default compiler name and flags
which are likely to work with the known-available compiler.
This is also a convenience for users who may not know what arguments
cl.exe may need to compile the tests.
Changes since v1:
- Use "-option" instead of "/option" to avoid issues running under msys.
- Disable C4200 warning for use of flexible array members, which MSVC
considers an extension (since it does not fully support C99).
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:45 +0000 (18:44 -0600)]
configurator: Add output cflag option and macro
Unfortunately, not all compilers support -o as a command-line option for
specifying the output file. Visual Studio cl.exe issues warning D9035
when -o is given, which is detected as a compile warning by the
configurator.
To support such compilers, add the command-line option -O to
configurator which can be used to specify the cflag for setting the
output executable file name. Additionally define the macro
CCAN_OUTPUT_EXE_CFLAG in config.h and use it when invoking the compiler
(e.g. from ccanlint).
For reference, the name CCAN_OUTPUT_EXE_CFLAG was chosen to avoid
potential name conflicts in the future due to cl.exe requiring different
flags for different types of output[1] (e.g. object files are /Fo:).
Kevin Locke [Thu, 29 Sep 2016 00:44:44 +0000 (18:44 -0600)]
configurator: Print test source without cat
Windows does not provide cat. Instead, copy the test source to stdout
using the file stream to which it was written.
Changes since v1:
- Create fwrite_noeintr to avoid EINTR in fwrite without writing any
data.
- Handle short reads from fread. This can happen with non-conformant
libc or if EINTR occurs after reading some data.
- Handle short writes from fwrite. This can happen with non-conformant
libc or if EINTR occurs after writing some data.
Changes since v2:
- Revert fwrite_noeintr and short read/write changes.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:43 +0000 (18:44 -0600)]
configurator: Inline err.h functions
On systems where err.h is not provided (e.g. MSVC) configurator must
provide its own definition. The err module can not be used by
configurator due to its dependency on config.h, so the relevant source
is copied into configurator with the minimum changes necessary.
Changes since v2:
- Use the CCAN err module sources instead of musl libc sources to avoid
introducing another implementation of these functions.
- Prefix err.h functions with "c12r_" to avoid name conflicts and
"static declaration follows non-static" errors.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Thu, 29 Sep 2016 00:44:42 +0000 (18:44 -0600)]
configurator: Reimplement run using popen
Rather than using fork+pipe+system+waitpid, most of which are only
available on POSIX-like systems, use popen which is also available on
Windows (under the name _popen).
Changes since v1:
- Create fread_noeintr to avoid EINTR in fread without reading any data.
- Handle short reads from fread. This can happen with non-conformant
libc or if EINTR occurs after reading some data.
- Define _POSIX_C_SOURCE for popen/pclose with strict implementations
which require it (e.g. gcc with -std=c11).
Changes since v2:
- Revert fread_noeintr and short read changes in v1 as unnecessary.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Fri, 23 Sep 2016 03:33:13 +0000 (21:33 -0600)]
configurator: Fix warning in HAVE_FOR_LOOP_DECLARATION
Visual C++ prints "warning C4702: unreachable code" due to the return
statement after the for loop which is never reached. Fix this by
setting a variable returned by a single return statement at the end.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Fri, 23 Sep 2016 03:33:10 +0000 (21:33 -0600)]
configurator: Fix compiler warning with compare
Visual Studio prints warning C4706 "assignment within conditional
expression" when there is an assignment without a comparison in a
conditional expression. Therefore, to silence the warning, add an
explicit comparison.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Reviewed-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Fri, 23 Sep 2016 03:33:08 +0000 (21:33 -0600)]
configurator: Mark non-Windows tests MAY_NOT_COMPILE
Several of the EXECUTABLE tests depend on headers not available on
Windows. Mark these tests MAY_NOT_COMPILE to handle this.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Reviewed-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Fri, 23 Sep 2016 03:33:07 +0000 (21:33 -0600)]
configurator: Use native directory separator
Although Windows APIs generally permit "/" or "\\" for directory
separators in paths, cmd.exe does not recognize "./" when invoking
executables using a relative path and prints the following error:
'.' is not recognized as an internal or external command,
operable program or batch file.
Therefore, use "\\" when invoking tests on Windows.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Reviewed-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
Kevin Locke [Fri, 23 Sep 2016 03:33:04 +0000 (21:33 -0600)]
configurator: Replace unlink with remove
Although Windows provides unlink, using it adds complication due to the
lack of unistd.h which must be included to define the function on POSIX
systems. Instead, use remove, which C89 requires to be in stdio.h.
Signed-off-by: Kevin Locke <kevin@kevinlocke.name> Reviewed-by: David Gibson <david@gibson.dropbear.id.au> Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
This is the same as list_empty but without the debug checks. This is
useful when wanting to check for an empty list without locks held,
potentially racing with addition/removal, which can be a valid thing
to do under some circumstances.
Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Jon Griffiths [Wed, 21 Sep 2016 01:56:08 +0000 (13:56 +1200)]
Remove travis workarounds for previous build system
With proper dependencies and parallel safety, we can just
'make check -j N' directly. Also build quietly so that we
only get build warnings, errors and test results in the output.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Jon Griffiths [Thu, 1 Sep 2016 09:24:36 +0000 (21:24 +1200)]
Makefile: First try at rewriting the ccan Makefile.
This change contains a simpler Makefile replacement with only 62 lines
of directives, 10 rules, and a 13 line support script for dependencies. The
build dependencies have been minimised and in some cases, corrected.
FEATURES:
* All targets can be built from a clean tree in one invocation.
* Parallel builds (tested with -j32 on 8 cores).
* Auto discovery of modules via _info files.
* Hopefully complete dependencies via a simplified generator.
* CFLAGS are respected and appended to compile flags.
* LINTFLAGS can be set to add check options (e.g. LINTFLAGS=-v).
* 'make clean' doesn't build anything before cleaning now.
* 'make quiet=1' builds quietly. 'make check quiet=1 -j N' produces
summary output like the former summary target.
* Non-phony test targets; tests are rebuilt only when dirty. Targets are:
check, fastcheck and fullcheck, the latter runs in non-summary mode.
* 'make <module>.[check|fastcheck|fullcheck]' runs tests for single modules.
TODO:
* Support Makefile-web and any other scattered targets
NOTES:
* The changes to dependency generation expose a circular
dependency between asort and order which is not fixed here.
* Tests always run their dependent tests. With -j support and
minimised rebuilds via tighter dependencies, its not worth avoiding.
* Some targets have been dropped as uneeded (e.g. distclean, tools).
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Rusty Russell [Wed, 7 Sep 2016 04:27:01 +0000 (13:57 +0930)]
tal: make tal_next() only return immediate children.
I tried to use it and got this wrong: moreover, I wanted to control
topology, which requires nested iteration, and skip children
of a node which I knew was changing.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Jon Griffiths [Sun, 28 Aug 2016 23:43:39 +0000 (11:43 +1200)]
Add a SHA512 implementation
This largely follows the SHA256 style. I've named Rusty as the maintainer.
Currently the functions to add data of various sizes/endianness have not
been implemented: There are no public test vectors for these cases and
I believe most use cases are working on byte buffers. They can be added
later if desired.
The openssl implementation has been tested on x86-64, while the inbuilt
version has been tested on 32/64 bit, little/big endian boxes.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Rusty Russell [Tue, 30 Aug 2016 00:35:06 +0000 (10:05 +0930)]
tools/ccanlint: test_depends_accurate: catch #include of other ccan C files.
Jon sent a test patch for sha256 which "#include <ccan/str/hex/hex.c>"
without adding str/hex to testdepends. It "worked" (it wouldn't have
linked with "hex.h"), but ccanlint didn't spot the dependency.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
Jon Griffiths [Wed, 24 Aug 2016 06:44:12 +0000 (18:44 +1200)]
strmap: Set the license for strmap to CC0
This matches the license in _info and the source. It also means every
module now has a LICENSE file and so anyone happening to rewrite the
ccan makefiles can use wildcard to locate modules rather than listing
them by hand.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Jon Griffiths [Mon, 29 Aug 2016 01:10:29 +0000 (13:10 +1200)]
Ensure config.h is created before the main travis builds
The current makefiles are not parallel safe and reliably fail on the
clang build. The real fix is to rewrite the makefiles, but in the
meantime, allow the clang tests to pass.
Jon Griffiths [Sun, 28 Aug 2016 23:52:44 +0000 (11:52 +1200)]
sha256: Simplify test
We can use the iteration count in the test case to determine
whether a single call is required. This simplifies the code and
also means that we don't overstate the actual number of tests
performed by a factor of 2. Simplify a couple of expressions
while we are changing this.
Jon Griffiths [Mon, 22 Aug 2016 14:04:06 +0000 (02:04 +1200)]
tlist: Place tlists last in structures
TCON suggests placing _tcon members last in structs. Placing variable
sized structs anywhere but last is apparently a gcc extension that
gives warnings under clang.
This applies to tlists because they use TCON internally. Update the
docs and examples to place tlists last and so compile without clang
warnings.
There are other places where this occurs; they will be dealt with
separately.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Jon Griffiths [Mon, 30 May 2016 12:39:10 +0000 (00:39 +1200)]
hex: Simplify hex_encode
The documentation for hex_encode indicates that it returns simply true or
false. The old implementation was returning the written length on success,
cast to boolean. This will elicit a warning under MSVC.
On further examination, there is no need to check/modify the length inside
the loop, since we can check it once before starting. As a result the code
can be simplified a bit.
A side affect of this change is that nothing will be written at all if the
length is incorrect, vs the previous code writing characters until the length
available is exhausted. I prefer the new semantics but YMMV.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
Jon Griffiths [Tue, 22 Mar 2016 22:54:50 +0000 (11:54 +1300)]
sha256: Move 'bytes' to the end of sha256_ctx and make it a size_t
The code already assigns to/from bytes as a size_t, so make it
official (and better on platforms with a 32 bit size_t).
Moving bytes makes it act as a canary in the event that there is a rogue
write/off by one somewhere - since it ends up in the hash we are
more likely to detect this should we corrupt it. This also makes the
working buffer better aligned which can't hurt.
Also, initialise the buffer to zero while we are changing the initialisation
macro anyway. It costs little compared to the hashing overhead, should be
optimised away if redundant in most cases, and it removes a warning from both
gcc and clang about unititialised struct members.
Signed-off-by: Jon Griffiths <jon_p_griffiths@yahoo.com>
projects / ccan / log