Generic Data Structures

[elazarg]

Decompose the data structures into domain-specific and generic data structures.

The ds package has zero dependencies, and it knows nothing about numbers or network.

Interfaces (all in interfaces.go):

• Comparable (Equal, Copy)
• Hashable (Comparable, Hash)
• Set (Hashable + set operations)
• Product of A x B (partitions, left and right projections, swap)
• TripleSet, convenience (and associativity agnostic) interface for A x B x C

Implementations:

• HashMap - a simple adapter around a go map, allowing Hashable keys.
• HashSet
• MultiMap is a non-injective map. It gives a simple "inverse" on a HashMap.
• ProductLeft and ProductRight is a map-based implementation of a cartesian product; it implements Product as a one-to-one mapping from sets to sets, where each key-value pairs encodes the cross product of its two items.
• TripleSetLeft and TripleSetRight and TripleSetOuter are right-, left- and outer-associative implementations of TripleSet.
• DisjointSum is tagged-union of two sets. Go's generics place some limitations on the implementation; The empty element must always be explicitly passed to the constructor.
• UnitSet is an idea - using sets of size 1 as the identity element of Product. It's probably not really helpful.

The interval package has interval and intervalset. Nothing particularly new about them.

netp is unchanged.

The netset package is where handles sets of network elements.

• ICMPSet is largely the one proposed in #23.
• IPBlock is adapted to implement Set.
• TCPUDPSet is a TripleSet of ProtocolSet x PortSet x PortSet
• TransportSet is a disjoint union of TCPUDPSet + ICMPSet
• ConnectionSet is a TripleSet of IPBlock x IPBlock x TransportSet

The package connection now contains the state-aware connectionset (named Set), and its json-formatting. In my opinion it should be moved to the analyzer.

Many tests are adapted. but some data structures do not have dedicated tests.

There is no implementation of a dynamically-bounded tuple, since I could not find the proper way to fit that into a generic datastructure with a well defined degenerate edge case.

The diff is probably not useful; it should be easier to read the code.

[elazarg]

We may need to use ordered maps instead of hash maps, so the lists of partitions are consistently ordered.

[elazarg]

Added an elaborated README, and changed implementation of MultiMap to use HashSet.

[elazarg]

BTW, I think the class ICMP is better named ICMPRule, and is a set. The file icmp.go in the netp package should only have functions that are related to ICMP proper. Such change would also solve the need to expose implementation details of the ICMP class to the ICMPSet class.

[elazarg]

@adisos is there anything left for me to implement/document so this PR can be merged?

[adisos]

@adisos is there anything left for me to implement/document so this PR can be merged?

added few small comments, still reviewing the tests and some implementation details.

[elazarg]

I've improved and fixed the documentation of interface.go. @adisos please re-review this part.

Additionally, I've improved the interval package.

interval:

• Separate tests from interval_test.go
• Improve documentation.
• Export and set-like functions that are well defined.
• Rename interval.Subtract to interval.SubtractSplit, and add tests.
• Handle empty cases first.
• Preallocate Elements.

intervalset:

• Guard Size() from overflow, and use intervalset.CalculateSize().
• Handle empty cases first.
• Remove String() method, since it is not obvious; clients should implement.

---

I think it's better to make GenericInterval and GenericCanonicalSet as generic types (with integral constraints), so clients can choose whether or not to rely on things like Size() being 64bit integer. interval.Interval should be an alias to GenericInterval[int], and interval.Set should be an alias to GenericCanonicalSet[int].