+ cmb(1,3): Fix broken handling of -i num when given -k -1
+ cmb(3): Remove a stray newline
+ cmb(3): Add show_empty option for including the empty-set
+ cmb(1): Add -e option for showing the empty-set

Thanks! I have a huge update coming this month that will bring in lots of changes. Hoping you could revisit just afterward.

In pkg we have a SAT solver. Can you explain how your CMB compares to a SAT solver?

In D16132#498554, @hselasky wrote:

In pkg we have a SAT solver. Can you explain how your CMB compares to a SAT solver?

"SAT solvers are algorithms for discovering satisfactory Boolean assignments – or proving that none exist. Such solvers are of growing practical importance, in part because a host of significant combinatorial problems can be reduced to SAT problems" [1]

Not all combinatorial problems have been reduced to SAT problems yet all SAT problems are in the realm of combinatorics.

CMB provides a generalized and abstract substrate to which one can build existing and not-yet-imagined solvers upon.
CMB is a powerful library interface and command-line utility that facilitates tackling a near-unlimited number of combinatorial problems.

[1] https://sinews.siam.org/Details-Page/donald-knuth-talks-satisfiability-and-combinatorics

Returning to this, as I still want to add it to base.

The salient point that I would like to make here, with respect to SAT solvers, is that:

CMB is not a solver

It was not written to solve equations. It was written to give scope on combinatoric problems and enumerate combinations for actions.

For example, the build-option survey is not trying to solve an equation but test for combinations of build-options that break the build when combined together.

In example, if one has 32,000 build-options, cmb can first tell you how many combinations pairs-of-2 would result in, allowing you to determine whether it is worth your time.

cmb -t -r -k 2 32000

The result of the above command tells me that there are 511,984,000 combinations for "choose-2 from 32,000 items."

So right there, cmb was able to answer a question of whether it's even worth doing a build-option survey of all-known options (which I am sure there are less than 32,000 build options) choosing only combinations-of-2.

I am not trying to solve an equation but get a handle on the scope of the issue which is wanting to know which pairings of build options are broken.

Secondly, once you land on a set of combinations that you want to iterate over, cmb will help you iterate over them (and also resume where you left-off if you prematurely terminate and also help you parallelize the process or even distribute it amongst multiple systems).

For example:

cmb -e -N -k 1..2 -- -{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}

Produces:

1 
2 -a
3 -b
4 -c
5 -d
6 -e
7 -f
8 -g
9 -h
10 -i
11 -j
12 -k
13 -l
14 -m
15 -n
16 -o
17 -p
18 -a -b
19 -a -c
20 -a -d
21 -a -e
22 -a -f
23 -a -g
24 -a -h
25 -a -i
26 -a -j
27 -a -k
28 -a -l
29 -a -m
30 -a -n
31 -a -o
32 -a -p
33 -b -c
34 -b -d
35 -b -e
36 -b -f
37 -b -g
38 -b -h
39 -b -i
40 -b -j
41 -b -k
42 -b -l
43 -b -m
44 -b -n
45 -b -o
46 -b -p
47 -c -d
48 -c -e
49 -c -f
50 -c -g
51 -c -h
52 -c -i
53 -c -j
54 -c -k
55 -c -l
56 -c -m
57 -c -n
58 -c -o
59 -c -p
60 -d -e
61 -d -f
62 -d -g
63 -d -h
64 -d -i
65 -d -j
66 -d -k
67 -d -l
68 -d -m
69 -d -n
70 -d -o
71 -d -p
72 -e -f
73 -e -g
74 -e -h
75 -e -i
76 -e -j
77 -e -k
78 -e -l
79 -e -m
80 -e -n
81 -e -o
82 -e -p
83 -f -g
84 -f -h
85 -f -i
86 -f -j
87 -f -k
88 -f -l
89 -f -m
90 -f -n
91 -f -o
92 -f -p
93 -g -h
94 -g -i
95 -g -j
96 -g -k
97 -g -l
98 -g -m
99 -g -n
100 -g -o
101 -g -p
102 -h -i
103 -h -j
104 -h -k
105 -h -l
106 -h -m
107 -h -n
108 -h -o
109 -h -p
110 -i -j
111 -i -k
112 -i -l
113 -i -m
114 -i -n
115 -i -o
116 -i -p
117 -j -k
118 -j -l
119 -j -m
120 -j -n
121 -j -o
122 -j -p
123 -k -l
124 -k -m
125 -k -n
126 -k -o
127 -k -p
128 -l -m
129 -l -n
130 -l -o
131 -l -p
132 -m -n
133 -m -o
134 -m -p
135 -n -o
136 -n -p
137 -o -p

You can process the list sequentially or in-parallel or in distribution fashion because each combination has a deterministic index that is reproducible. Combination number 120 is "-j -n" for example. If you were processing this list of potential flag combinations (for whatever -- compiling, running, whatever) sequentially and you bailed on combination 120, you can resume from that point (example below):

cmb -e -N -k 1..2 -i 120 -- -{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}

Produces:

120 -j -n
121 -j -o
122 -j -p
123 -k -l
124 -k -m
125 -k -n
126 -k -o
127 -k -p
128 -l -m
129 -l -n
130 -l -o
131 -l -p
132 -m -n
133 -m -o
134 -m -p
135 -n -o
136 -n -p
137 -o -p

Or if you just needed that single combination (for example, if you were processing combinations in-parallel or in distributed fashion):

cmb -e -k 1..2 -i 120 -c 1 -- -{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}

Produces combination number 120:

-j -n

So while it is perhaps convenient to think that CMB is using combinatorics to solve equations and therefore can be relegated to being an insignificant offering (compared to SAT solvers), attempting to use a SAT solver to the above is a non-starter because SAT solvers are always trying to find short-cuts but for tasks like those above, there is no shortcut. In the above-case, you cannot know whether a combination of compile-time options are incompatible with each other unless you actually try and build with them.

When attempting to solve problems like that above, no tool exists in base to facilitate such testing. Not seq, nor jot, nor any other base command-line utility in FreeBSD, Linux, or any UNIX for that matter attempts to solve this problem.

It is in this light that I offer a solution that is easy to use, efficient, and powerful. Just like seq, jot, and other utilities which are not designed to solve a specific problem but provide the ability to perform required actions (specifically enumerative actions).

I'm going to set an ETIMEOUT of 30 days. If there is no objection, I will import to base HEAD.

Re-iterating the reasons why this should bypass ports and go to base:

This tool is being developed to ultimately aid base and ports functionality. If it exists in ports, it becomes like dialog4ports and has to be installed before you can extract all the functionality of ports.

I have ports that I want to use this in the Makefile and tools for base that I need to use this in (the build option survey, for example). Putting this in ports complicates those endeavors.

In D16132#550827, @dteske wrote:

I'm going to set an ETIMEOUT of 30 days. If there is no objection, I will import to base HEAD.

Re-iterating the reasons why this should bypass ports and go to base:

This tool is being developed to ultimately aid base and ports functionality. If it exists in ports, it becomes like dialog4ports and has to be installed before you can extract all the functionality of ports.

I have ports that I want to use this in the Makefile and tools for base that I need to use this in (the build option survey, for example). Putting this in ports complicates those endeavors.

Hi Devin,

Could you elaborate more on your planned uses of this code in the base system? The build option survey looks to me like something that would live in tools/, in which case it is reasonable to depend on a port. We keep python scripts there, for example. The mailing list thread about cmb(1) and libcmb seemed to conclude with the suggestion that they be added as a port, but I can't seem to find one.

Hi markj,

Yes, it was suggested that I make a port first.

However, everybody seems to be ignoring what I am saying regarding the utility of this tool being equitable to seq, jot, and friends.

Just yesterday, I did the following:

cmb -d / {a..z} | xargs stat 2>&1 | dpv -l -

The purpose was to generate millions of stat errors so that I could work on some filesystem patches to improve the performance of stat in nfsd.

Could I have used jot? Maybe, but it would have been more difficult.
Could I have used seq? Maybe, but same problems as jot. I needed discretely unique test matter.

I have been ignoring the suggestion to put it into ports because not one single person has even addressed the use-cases for base.

How would one make an argument for jot or seq being in base? If you pretend that they are not in base, what arguments would you use to introduce them?

cmb is kind of like that -- it has a million uses. Asking why we should have it in base is kind of like asking why we should have bc in base.

cmb is a math tool. A very powerful tool that fills a myriad requirements, not to mention the following use-case which I will once-again reiterate that has once again been ignored ...

I don't care about the build option survey. It was an example.

I care about using this for combinatoric combination of ports given various options.

Let's talk about dialog4ports -- a tool that lives in ports that is required by ports. So many times this has caused me headaches and I really don't want to go down that road. It is very frustrating when you get into a situation where ports needs X from ports but you can't compile it because your base and ports frameworks have diverged so you then have to devolve into first updating your base shared Mk files relied-on by ports. It's real shit-show.

Putting cmb in base will allow it to:
a. solve math problems
b. allow me to work on base enhancements with only base (think Filesystem debugging, filesystem optimizations, memory testing, scheduler profiling, etc.)
c. be usable by ports without being stuck in the quagmire-catch-22 described above

In D16132#564913, @dteske wrote:

Hi markj,

Yes, it was suggested that I make a port first.

However, everybody seems to be ignoring what I am saying regarding the utility of this tool being equitable to seq, jot, and friends.

Just yesterday, I did the following:

cmb -d / {a..z} | xargs stat 2>&1 | dpv -l -

The purpose was to generate millions of stat errors so that I could work on some filesystem patches to improve the performance of stat in nfsd.

Could I have used jot? Maybe, but it would have been more difficult.
Could I have used seq? Maybe, but same problems as jot. I needed discretely unique test matter.

I have been ignoring the suggestion to put it into ports because not one single person has even addressed the use-cases for base.

How would one make an argument for jot or seq being in base? If you pretend that they are not in base, what arguments would you use to introduce them?

cmb is kind of like that -- it has a million uses. Asking why we should have it in base is kind of like asking why we should have bc in base.

cmb is a math tool. A very powerful tool that fills a myriad requirements, not to mention the following use-case which I will once-again reiterate that has once again been ignored ...

I don't care about the build option survey. It was an example.

I care about using this for combinatoric combination of ports given various options.

Let's talk about dialog4ports -- a tool that lives in ports that is required by ports. So many times this has caused me headaches and I really don't want to go down that road. It is very frustrating when you get into a situation where ports needs X from ports but you can't compile it because your base and ports frameworks have diverged so you then have to devolve into first updating your base shared Mk files relied-on by ports. It's real shit-show.

Putting cmb in base will allow it to:
a. solve math problems
b. allow me to work on base enhancements with only base (think Filesystem debugging, filesystem optimizations, memory testing, scheduler profiling, etc.)
c. be usable by ports without being stuck in the quagmire-catch-22 described above

Regarding the prior discussion, I just see that the original thread on -announce appears to end with you saying that you would make a port. That didn't happen, and since there was some objection to putting cmb and libcmb straight into the base system, we should make sure that those objections won't be raised again after a commit. The right way to do that is to follow up on the lists, like -hackers and -arch, since only a small handful of developers are subscribed to this review.

I understand that cmb is intended to be a general-purpose utility, but that alone is not sufficient for putting it in the base system. jot(1) and seq(1) make for an interesting comparison since seq's functionality is a subset of jot's; seq was added to the base system relatively recently, specifically to make us more compatible with other unix environments. jot predates FreeBSD and comes from a time where a batteries-included approach to shipping an OS was more important than it is today.

I personally think that cmb would be an interesting addition to the base system, but there should be some concrete justification for it to be there. The build option survey is not really a compelling example. A ports target that builds a port with all possible combinations of options seems useful, but is there currently some work in progress to implement that? I understand that having the ports framework depend on a port is painful, but unless the absence of cmb from the base system is currently blocking a useful project, I don't see why this is a strong argument for not making a cmb port. You've written a number of large sh-based components of the base system - could any of them make use of cmb? My point is just that I believe that you could successfully argue for cmb's inclusion in the base system, but the idea first needs to be socialized more fully. A port is a reasonable alternative in the meantime and will make it easy for others to try using cmb.

In D16132#565399, @markj wrote:

In D16132#564913, @dteske wrote:

Hi markj,

Yes, it was suggested that I make a port first.

However, everybody seems to be ignoring what I am saying regarding the utility of this tool being equitable to seq, jot, and friends.

Just yesterday, I did the following:

cmb -d / {a..z} | xargs stat 2>&1 | dpv -l -

The purpose was to generate millions of stat errors so that I could work on some filesystem patches to improve the performance of stat in nfsd.

Could I have used jot? Maybe, but it would have been more difficult.
Could I have used seq? Maybe, but same problems as jot. I needed discretely unique test matter.

I have been ignoring the suggestion to put it into ports because not one single person has even addressed the use-cases for base.

How would one make an argument for jot or seq being in base? If you pretend that they are not in base, what arguments would you use to introduce them?

cmb is kind of like that -- it has a million uses. Asking why we should have it in base is kind of like asking why we should have bc in base.

cmb is a math tool. A very powerful tool that fills a myriad requirements, not to mention the following use-case which I will once-again reiterate that has once again been ignored ...

I don't care about the build option survey. It was an example.

I care about using this for combinatoric combination of ports given various options.

Let's talk about dialog4ports -- a tool that lives in ports that is required by ports. So many times this has caused me headaches and I really don't want to go down that road. It is very frustrating when you get into a situation where ports needs X from ports but you can't compile it because your base and ports frameworks have diverged so you then have to devolve into first updating your base shared Mk files relied-on by ports. It's real shit-show.

Putting cmb in base will allow it to:
a. solve math problems
b. allow me to work on base enhancements with only base (think Filesystem debugging, filesystem optimizations, memory testing, scheduler profiling, etc.)
c. be usable by ports without being stuck in the quagmire-catch-22 described above

Regarding the prior discussion, I just see that the original thread on -announce appears to end with you saying that you would make a port. That didn't happen, and since there was some objection to putting cmb and libcmb straight into the base system, we should make sure that those objections won't be raised again after a commit. The right way to do that is to follow up on the lists, like -hackers and -arch, since only a small handful of developers are subscribed to this review.

I understand that cmb is intended to be a general-purpose utility, but that alone is not sufficient for putting it in the base system. jot(1) and seq(1) make for an interesting comparison since seq's functionality is a subset of jot's; seq was added to the base system relatively recently, specifically to make us more compatible with other unix environments. jot predates FreeBSD and comes from a time where a batteries-included approach to shipping an OS was more important than it is today.

I personally think that cmb would be an interesting addition to the base system, but there should be some concrete justification for it to be there. The build option survey is not really a compelling example. A ports target that builds a port with all possible combinations of options seems useful, but is there currently some work in progress to implement that? I understand that having the ports framework depend on a port is painful, but unless the absence of cmb from the base system is currently blocking a useful project, I don't see why this is a strong argument for not making a cmb port. You've written a number of large sh-based components of the base system - could any of them make use of cmb? My point is just that I believe that you could successfully argue for cmb's inclusion in the base system, but the idea first needs to be socialized more fully. A port is a reasonable alternative in the meantime and will make it easy for others to try using cmb.

I've had time to think about this and I believe the proper justification for being in base is to classify the behavior that it provides as missing functionality in the category of "text expanders/modifiers" which would include (as part of the base system):

glob(3)
fnmatch(3)
ls(1)
sh(1)
jot(1)
seq(1)
expand(1)
rs(1)
pr(1)
awk(1)
sed(1)
col(1)

and arguably even:

vi(1)
ed(1)

and ilk. That is to say that cmb(1) and cmb(3) are ways of taking text and expanding it in a predictable way -- maybe not in a way that is readily obvious to most people, but I would argue that the functionality performed by tbl(1) is not readily obvious to most people (and in-fact may never be used directly by the majority of people).

That being said, you are right that I should find some use-case for it in bsdconfig or some other tool already living in base first to demand its import to the base system.

In D16132#626980, @gbe wrote:

LGTM for the man page related things.

Thanks!

In D16132#711222, @pstef wrote:

Looks good to me.

I'm playing with this utility on my stable/13 and I like the idea very much. It feels unixy to me in that the tool is abstract enough for me to apply it to various problems which may be difficult to define beforehand. But I can already see myself using this instead of generating permutations with recursive CTEs in SQL like I sometimes do.

Also, although I'm not sure anyone will find this meaningful, cmb reminds me of a problem I was solving recently at job, feeding a Cassandra table random data:

The table and its keyspace were defined as follows:
CREATE KEYSPACE test WITH REPLICATION = { 'class' : 'SimpleStrategy', 'replication_factor' : 1 };
CREATE TABLE test.base(part text, ord text, fill text, PRIMARY KEY((part), ord));

We feed the table like this:
# base32 -w 2000 < /dev/urandom | cut -b1-3,4-8,9- --output-delimiter=, | cqlsh -u $CASS_USER -e 'COPY test.base FROM STDIN'

Cutting base32 output into columns of arbitrary length gives us control over cardinality of each column; specifically we want to know the upper bound on the number of partitions and the number of rows in each partition. Given a set of k (32 in base32) characters, the number of n-tuples (n characters in a column) is k^n. For example, taking the first 3 letters of each line to use in the partitioning column gives us the upper bound of 32^3 partitions, which is 32768.

Forgive the verbosity and being Ubuntu-specific (base32, cut --output-delimiter, /dev/urandom), but I hope you get the idea: I tend to use unix tools when interacting with other tools or services, databases especially.

By the way, the util and the library seem small enough:

-r-xr-xr-x  1 root  wheel    46K Aug  5 14:17 /usr/bin/indent
-r--r--r--  1 root  wheel    21K Aug 15 17:49 /usr/lib/libcmb.so.0
-r-xr-xr-x  1 root  wheel    31K Aug 15 17:50 /usr/bin/cmb

Thank you pstef! I am going to try and think up a way to incorporate this into something already in base, like sysrc, bsdconfig, bsdinstall, or something else I have written to help bring it in.

Oh, I missed that there was a new review a couple years ago. I am more than happy to dust this off. I was just talking about this to a coworker last night at the company holiday party.

Oh, this is cool!

In D16132#947866, @pstef wrote:

As of stable/14 this no longer compiles for me due to

/usr/src/lib/libcmb/cmb.c:854:6: error: invalid argument type 'void' to unary expression
        if (!BN_zero(count))
            ^~~~~~~~~~~~~~~
/usr/src/lib/libcmb/cmb.c:1032:7: error: invalid argument type 'void' to unary expression
                if (!BN_zero(seq))
                    ^~~~~~~~~~~~~
2 errors generated.

Thank you so much.

Here's what I have been doing lately, but need to really determine which version of OpenSSL that changed the BN_zero() function from returning something to returning nothing.

diff
--- a/depend/libcmb/cmb.c
+++ b/depend/libcmb/cmb.c
@@ -851,8 +851,12 @@ cmb_count_bn(struct cmb_config *config, uint32_t nitems)
 	/* Initialize count */
 	if ((count = BN_new()) == NULL)
 		return (NULL);
+#if 0
 	if (!BN_zero(count))
 		goto cmb_count_bn_return;
+#else
+	BN_zero(count);
+#endif
 
 	/* If entire set is requested, return 2^N[-1] */
 	if ((setinit == 1 && setdone == nitems) ||
@@ -1029,8 +1033,12 @@ cmb_bn(struct cmb_config *config, uint32_t nitems, char *items[])
 	if (seq == NULL) {
 		if ((seq = BN_new()) == NULL)
 			goto cmb_bn_return;
+#if 0
 		if (!BN_zero(seq))
 			goto cmb_bn_return;
+#else
+		BN_zero(seq);
+#endif
 	}
 
 	/* Show the empty set consisting of a single combination of no-items */

I'm working on updating this to incorporate the suggestions from folks.

Just taking a quick pass after you pointed me at the review -- I really like this idea -- solid :)!

I would steer clear of naming variables nitems in the code because we have a macro that is named that already in sys/param.h.