Our Dsatur implementation was incorrect: while the paper defined the
degree of saturation of a vertex as the number of different colors it is
adjacent to, we were using the number of colors, without considering
uniqueness. This effectively implemented a different algorithm, which is
very similar to the previous one, and while it performs slightly worse
on average it still beats Dsatur on some cases.

So we refactor the implementation to effectively support both algorithms
without code duplication, and then we export both the old algorithms as
"Dcolor" and the new one as "Dsatur". Since these are all fast
algorithms in hroller we will still be able to pick the best result.

Note that the new Dsatur implementation uses an IntSet to calculate the
uniqueness. Results with nub + length on a list were significantly
slower.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This function helps treating node node problems as graph problems.
It can transform a list of nodes plus a list of instances into a graph
which uses the nodes as vertices, and instances as edges connecting them
(as long as they have both a primary and a secondary node)

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This brings our coverage of Graph.hs to 100%

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

Check whether coloring on a given graph makes sense. This is the case
only if there are no loops and the graph is undirected.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

Implement the Dsatur algorithm for Graph coloring. This also abstracts
the neighColors function into two subfunctions that this algorithm can
reuse.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This module implements some algorithms on Data.Graph data structures.
At the moment its main functionality is an LF-color implementation
(greedy coloring in descending order of degree). There are also a few
extra functions to calculate the degree order, and convert the node to
color mapping to color to nodes.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This patch adds the "meta" opcode type and the common op
params. Compatibility tests with Python are changed to pass Meta
opcodes.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

This will go into a separate type; this patch adds the needed
underlying types and parameters.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

This mirrors the positive one, and will be needed for relative job
IDs.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

Currently, the job ID is a simple type alias. This is suboptimal, as
it means we can't use a custom JSON (or Arbitrary) instance for it.

The patch changes it into a newtype, and then a) simplifies some
deserialisation code and b) changes some more fields to this new type
(rather than plain 'Int').

We also move the JobId to types, since it will be needed in opcodes as
well.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

For now, we don't need a pending job status type as well, so we'll
delay adding that until later.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

As opposed to the existing test, which tests the type/serialisation of
fields, this one simply tests the equivalence of the list of fields
for each opcode.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

Commit 213076fe (“Fix locking in networks”) changed Python OpNetworkAdd
without corresponding Haskell definition changes.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

Due to manual conversion, a few fields were missing from the
conversion, but as they were optional our type equivalence checking
didn't detect this.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

The original htools opcodes were minimalistic and not 1:1 equivalent
with the Python ones. Let's add all missing fields and, since we
changed the order, switch to more readable record syntax for building
the opcodes.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

The current uniqueness algorithm (generate random node names, suffix
them with node index) is actually wrong: a node named "21" at index 5
will end up with the same name as a node named "2" at position 15.

To fix this, we also add a character from a different "set" ("-"), so
that such mixups can't happen again, and also add an explicit check
for it.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Michael Hanselmann <hansmi@google.com>

The serialization itself is done by Text.JSON, so the tests deal with checking
that Text.JSON objects are created correctly from the DRBD parser data
structures.

Signed-off-by: Michele Tartara <mtartara@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

The serialized JSON is not a 1:1 dump of the data structures
populated by the parser. This is done intentionally, with the
aim of producing a more stable and more meaningful output to
be used by the (future) monitoring agent and stand-alone data
collectors.

Also:
* shorten the names of some data types.
* change data type for the fields of the Time data structure

Signed-off-by: Michele Tartara <mtartara@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This improves Issue 325 - new runtime and memory consumption is about
1/10 compared to before.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Guido Trotter <ultrotter@google.com>

Given a node list in input, we get an instance that had nodes in it.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This takes an instance generator and produces a possibly empty list of
instances.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This generates a minimum of one node, because legal clusters never have
zero nodes.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

This is used only once when testing Cluster.hs, but having it abstracted
clarifies there what that call is about, makes that test shorter, and
allows us to better do refactoring of the main genInstanceSmallerThan
generator.

Signed-off-by: Guido Trotter <ultrotter@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

I've been bitten a couple of times with arbitrary opcodes working on
UTF-8 locale, but failing on buildbot (ASCII). So let's add an
explicit test that checks always (even with UTF-8) for correct
arbitrary values, showing explicitly which opcodes fail.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

It turns out that optimising 'read' derived instances (via -O) for
complex data types (like OpCode, or the various objects) can be slow
to very slow. Disabling such instances results in (time make
$all_our_haskell_binaries) large compile-time savings and also smaller
(unstripped) binaries (by a significant amount):

ghc 6.12:        time  htools sz  hconfd sz
  with read:    4m50s 12,244,694 14,927,928
  no read:      3m30s 10,234,305 12,536,745
ghc 7.6:
  with read:   14m45s 13,694,761 15,741,755
  no read:      3m40s 11,631,373 13,245,134

So let's remove these instances, since we never use read in production
for our custom types, and even when debugging in GHCI, we can simply
use the 'show' representation to create the types, without needing to
actually parse from strings.

Note: for the very slow ghc 7.6 compilation time, I filled a ticket
(ghc #7450), since it is surprising(ly slow).

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Michele Tartara <mtartara@google.com>

… except one, and replace them with separately-defined ones in
OpParams.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

It would be even better if the opcodes would actually have all the
same definitions, until then we have two sets of definitions.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

Due to lack of attention, we have two styles for generators of
arbitrary values: get* and gen* (e.g. getFQDN and genDiskIndices). In
order to make this more obvious that we deal with a function in the
Gen monad, let's rename all get* functions to gen*.

A few other simplifications were done on existing tests, switching to
helpers that were introduced later.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

This patch enhances the opcode list checks - instead of spawning a
Python interpreter to display the opcode list, we export it statically
in Constants.hs via a slight convert-constants change.

Furthermore, since we now have opcode parity, we enable full opcode
list checks.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

OpInstanceQuery was missing accidentally, whereas OpRestrictedCommand
was just recently added without Haskell definitions.

The patch also slightly improves the OpNodeQuery arbitrary generation.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

This completes the last missing opcode group. The only difficulty was
with the ip addresses, where we used simple strings to represent them
and (for IPv4) a few helpers to generate arbitrary instances;
otherwise, the patch is trivial.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

Also add some unittests for this type.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

This adds the OpTestAllocator, OpTestJqueue and OpTestDummy
opcodes. The OpTestAllocator seems to need some cleanup (on the Python
side), for now we implement it as is. As for the other two, while not
used in production, we should have full coverage for them as well.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

The regexp in OpTagsSearch is loaded as is, without testing for
validity; the rest of the patch is trivial.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

This also corrects a docstring in OpBackupExport on the Python side.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

Only the original instance opcodes (used in htools) are left
non-converted to only parameter style; they'll be cleaned up later,
once the htools codebase itself migrates to safer types.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

This is a "big" opcode, so sending it separately.

A few types needed changing, and a few parameters were renamed to make
it more clear which are cluster-level and which are instance-level
parameters.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

Another base type that we need in opcodes as well.

Signed-off-by: Iustin Pop <iustin@google.com>
Reviewed-by: Helga Velroyen <helgav@google.com>

* Now the parser completely consumes the input, up to the end of the text.
* Name of the test suite module changed to adhere to naming conventions.
* Some reformatting of the source code.

Signed-off-by: Michele Tartara <mtartara@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>

The bug was in the test itself, not in the tested code.

Also, fixed a line longer than 80 characters in the same file.

Signed-off-by: Michele Tartara <mtartara@google.com>
Reviewed-by: Iustin Pop <iustin@google.com>