9 years agocyclegraph: expand template usage
Brian Norris [Thu, 7 Feb 2013 00:39:15 +0000 (16:39 -0800)]
cyclegraph: expand template usage

checkReachable() and addEdge() will be used in more forms. Add template

9 years agomodel: refactor to use a helper function
Brian Norris [Wed, 6 Feb 2013 23:46:23 +0000 (15:46 -0800)]
model: refactor to use a helper function

9 years agocyclegraph: don't delete promise nodes
Brian Norris [Wed, 6 Feb 2013 22:46:21 +0000 (14:46 -0800)]
cyclegraph: don't delete promise nodes

Merging can fail partway, leaving a somewhat inconsistent graph. This is
safe, since an inconsistent graph must be discarded as infeasible. But
this is a problem when dumping the modification order graph, since we
may dereference freed nodes. So for now, just don't free them.

9 years agocyclegraph: fixup support for dumping the modification order graph
Brian Norris [Wed, 6 Feb 2013 22:43:39 +0000 (14:43 -0800)]
cyclegraph: fixup support for dumping the modification order graph

We need to include promises in the modification order graph if we plan
on dumping it to a .dot file. This hacks it together so that it works
for now.

9 years agocyclegraph: mergeNodes(): return early if we violate RMW
Brian Norris [Wed, 6 Feb 2013 22:42:00 +0000 (14:42 -0800)]
cyclegraph: mergeNodes(): return early if we violate RMW

To be consistent, and to prevent unecessary merging work, we should
simply return from the mergeNodes() function as soon as we know it has

9 years agocyclegraph: refactor for indentation
Brian Norris [Wed, 6 Feb 2013 22:41:12 +0000 (14:41 -0800)]
cyclegraph: refactor for indentation

9 years agoMakefile / git: cleanup generated .dot and .pdf files
Brian Norris [Wed, 6 Feb 2013 22:00:05 +0000 (14:00 -0800)]
Makefile / git: cleanup generated .dot and .pdf files

9 years agocyclegraph: add wrappers for some common functionality
Brian Norris [Wed, 6 Feb 2013 02:27:35 +0000 (18:27 -0800)]
cyclegraph: add wrappers for some common functionality

9 years agomodel: fully utilize Promise nodes in CycleGraph
Brian Norris [Wed, 6 Feb 2013 01:45:31 +0000 (17:45 -0800)]
model: fully utilize Promise nodes in CycleGraph

We can eliminate the post-promise-resolution computations now that
mo_graph is built up to include Promise nodes.

9 years agomodel: cosmetic improvements to resolve_promises()
Brian Norris [Wed, 6 Feb 2013 01:39:36 +0000 (17:39 -0800)]
model: cosmetic improvements to resolve_promises()

Rename 'resolved' to 'haveResolved', since we will use the 'resolved'
name for something else.

9 years agocyclegraph: move function definitions out of header
Brian Norris [Wed, 6 Feb 2013 01:36:05 +0000 (17:36 -0800)]
cyclegraph: move function definitions out of header

I found out how to instantiate these functions from within the
implementation file (rather than the header). I can specifically list
those implementations that I want available.

9 years agocyclegraph: template-ize addRMWEdge()
Brian Norris [Wed, 6 Feb 2013 01:13:28 +0000 (17:13 -0800)]
cyclegraph: template-ize addRMWEdge()

9 years agocyclegraph: bugfix - pop edges properly
Brian Norris [Tue, 5 Feb 2013 22:26:24 +0000 (14:26 -0800)]
cyclegraph: bugfix - pop edges properly

Now that CycleNode's have back-edges, we need to properly remove *both*
the forward and back edges when doing roll-back.

9 years agomodel: add write-to-promise edges
Brian Norris [Tue, 5 Feb 2013 22:10:06 +0000 (14:10 -0800)]
model: add write-to-promise edges

Assume that any time a promise exists, is compatible with a store, and
is exclusive to the same thread as the store, that it is mod-ordered
after that store. This should never produce cycles, until we decide to
begin satisfying promises. At that point, if there's a cycle, then we
must either merge nodes (i.e., the store must satisfy that promise) or
else we discard the execution for the moment and perform the
satisfaction at a later point in the search space.

9 years agopromise: add is_compatible_exclusive()
Brian Norris [Tue, 5 Feb 2013 22:03:28 +0000 (14:03 -0800)]
promise: add is_compatible_exclusive()

Check if a Promise is both compatible *and* exclusive to a particular
thread. This allows ordering optimizations when we can guarantee that a
particular thread must fulfill the promise.

9 years agopromise: add const
Brian Norris [Tue, 5 Feb 2013 22:01:34 +0000 (14:01 -0800)]
promise: add const

9 years agomodel: utilize CycleGraph 'addEdge()' status
Brian Norris [Tue, 5 Feb 2013 21:47:20 +0000 (13:47 -0800)]
model: utilize CycleGraph 'addEdge()' status

The mo_graph is only modified if addEdge() returns true. Utilize this

9 years agocyclegraph: return 'added' status for addEdge()
Brian Norris [Tue, 5 Feb 2013 21:44:32 +0000 (13:44 -0800)]
cyclegraph: return 'added' status for addEdge()

The ModelChecker would like to know if it's adding a new edge, or just
and existing edge. If the edge is not new, then there are fewer
resulting update checks needed.

9 years agocyclegraph: add documentation
Brian Norris [Tue, 5 Feb 2013 06:50:45 +0000 (22:50 -0800)]
cyclegraph: add documentation

9 years agocyclegraph: bugfix - only use concrete writes to eliminate threads
Brian Norris [Tue, 5 Feb 2013 01:12:11 +0000 (17:12 -0800)]
cyclegraph: bugfix - only use concrete writes to eliminate threads

9 years agocyclegraph: edit template for checkReachable
Brian Norris [Tue, 5 Feb 2013 00:24:36 +0000 (16:24 -0800)]
cyclegraph: edit template for checkReachable

9 years agocyclegraph: edit template for addEdge
Brian Norris [Tue, 5 Feb 2013 00:24:21 +0000 (16:24 -0800)]
cyclegraph: edit template for addEdge

9 years agocyclegraph: add overloaded getNode_noCreate()
Brian Norris [Tue, 5 Feb 2013 00:22:03 +0000 (16:22 -0800)]
cyclegraph: add overloaded getNode_noCreate()

Need a generic way to map a ModelAction/Promise to a CycleNode.

9 years agomodel: add promise-node edges for 'read' actions
Brian Norris [Sat, 2 Feb 2013 01:51:56 +0000 (17:51 -0800)]
model: add promise-node edges for 'read' actions

9 years agocyclegraph: template-ize checkReachable()
Brian Norris [Sat, 2 Feb 2013 01:47:57 +0000 (17:47 -0800)]
cyclegraph: template-ize checkReachable()

ModelChecker will need to query the mo_graph regarding the modification
order of promised future writes.

9 years agomodel: template-ize 'r_modification_order'
Brian Norris [Sat, 2 Feb 2013 00:44:22 +0000 (16:44 -0800)]
model: template-ize 'r_modification_order'

We will need to add "read modification order" edges when 'rf' is either
a ModelAction or a Promise. This function works nicely with a template.

9 years agoaction: fixup printing for RMW/RMWR
Brian Norris [Fri, 1 Feb 2013 23:33:38 +0000 (15:33 -0800)]
action: fixup printing for RMW/RMWR

Some read actions didn't really have a correct 'value' saved in the
ModelAction. Now that we have the 'promise' recorded, always retrieve
the value from reads_from or reads_from_promise.

9 years agoaction: store Promise in ModelAction
Brian Norris [Fri, 1 Feb 2013 23:27:32 +0000 (15:27 -0800)]
action: store Promise in ModelAction

9 years agocyclegraph: add full promise resolution, node merging
Brian Norris [Fri, 1 Feb 2013 23:11:13 +0000 (15:11 -0800)]
cyclegraph: add full promise resolution, node merging

We now support the interfaces needed for tracking Promise constraints in

9 years agocyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()
Brian Norris [Fri, 1 Feb 2013 23:09:07 +0000 (15:09 -0800)]
cyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()

9 years agopromise: add is_compatible()
Brian Norris [Fri, 1 Feb 2013 23:07:56 +0000 (15:07 -0800)]
promise: add is_compatible()

9 years agocyclegraph: map Promises to Promise nodes
Brian Norris [Tue, 29 Jan 2013 02:48:46 +0000 (18:48 -0800)]
cyclegraph: map Promises to Promise nodes

9 years agocyclegraph: template for addEdge()
Brian Norris [Tue, 29 Jan 2013 02:39:23 +0000 (18:39 -0800)]
cyclegraph: template for addEdge()

This function will be identical for all combinations of ModelAction /
Promise. So just make it a template.

9 years agocyclegraph: rename addEdge() to addNodeEdge()
Brian Norris [Tue, 29 Jan 2013 02:30:28 +0000 (18:30 -0800)]
cyclegraph: rename addEdge() to addNodeEdge()

This is a "low-level" internal function, where the other addEdge()
implementations will be high-level, external interfaces. Differentiate
the names, then.

9 years agocyclegraph: add removeEdge(), removeBackEdge()
Brian Norris [Sat, 26 Jan 2013 00:41:27 +0000 (16:41 -0800)]
cyclegraph: add removeEdge(), removeBackEdge()

For popping edges of a node that's about to be merged with another one.

Note that if using these functions, a user has to manage the
'CycleGraph::hasCycles' state. This only handles the inter-Node edge

9 years agocyclegraph: add Promise CycleNode
Brian Norris [Sat, 26 Jan 2013 01:19:55 +0000 (17:19 -0800)]
cyclegraph: add Promise CycleNode

A very bare-bones constructor.

9 years agocyclegraph: trivial shortening
Brian Norris [Wed, 6 Feb 2013 21:42:24 +0000 (13:42 -0800)]
cyclegraph: trivial shortening

9 years agoMakfile: add 'make pdfs' target to build PDF from .dot graph
Brian Norris [Tue, 5 Feb 2013 23:16:03 +0000 (15:16 -0800)]
Makfile: add 'make pdfs' target to build PDF from .dot graph

9 years agomodel: don't print scheduler randomly
Brian Norris [Wed, 6 Feb 2013 03:31:57 +0000 (19:31 -0800)]
model: don't print scheduler randomly

9 years agoaction: fix incorrect comment
Brian Norris [Sat, 2 Feb 2013 02:08:39 +0000 (18:08 -0800)]
action: fix incorrect comment

9 years agoDoxyfile: don't recurse into all directories
Brian Norris [Sat, 2 Feb 2013 01:18:32 +0000 (17:18 -0800)]
Doxyfile: don't recurse into all directories

9 years agocyclegraph: use vector empty() and clear()
Brian Norris [Wed, 30 Jan 2013 18:19:21 +0000 (10:19 -0800)]
cyclegraph: use vector empty() and clear()

9 years agonodestack/model: spacing
Brian Norris [Tue, 29 Jan 2013 18:15:44 +0000 (10:15 -0800)]
nodestack/model: spacing

9 years agopromise: update names/comments
Brian Norris [Sat, 26 Jan 2013 00:59:16 +0000 (16:59 -0800)]
promise: update names/comments

Make it more clear what 'act' is (it's a 'read' action).

9 years agocyclegraph: RMW atomicity violation must flag a cycle
Brian Norris [Fri, 25 Jan 2013 21:35:38 +0000 (13:35 -0800)]
cyclegraph: RMW atomicity violation must flag a cycle

Because we've removed some of the special-casing for RMW atomicity
violations, we don't need the separate 'hasRMWViolation' condition;
instead, we should explicitly flag atomicity violations as a cycle.
Previously, there was a subtle bug related to this issue, where cycles
were flagged only as RMW violations and did not show up to the
model-checker at the appropriate points.

9 years agocyclegraph: reformat, improve 'addRMWEdge' comments
Brian Norris [Fri, 25 Jan 2013 01:29:58 +0000 (17:29 -0800)]
cyclegraph: reformat, improve 'addRMWEdge' comments

Make it slightly clearer what this function's intent is. (It's only used
for the introduction of the first edge between 'from' and 'rmw' s.t.:

  from->is_write() && rmw->is_rmw() && from --rf-> rmw

9 years agocyclegraph: separate an 'addEdge(CycleNode *, CycleNode *) function
Brian Norris [Fri, 25 Jan 2013 01:26:28 +0000 (17:26 -0800)]
cyclegraph: separate an 'addEdge(CycleNode *, CycleNode *) function

We need to represent edge addition as a low-level operation on
CycleNodes, not just on ModelActions.

9 years agomodel: remove ModelChecker::is_infeasible_ignoreRMW()
Brian Norris [Fri, 25 Jan 2013 01:18:06 +0000 (17:18 -0800)]
model: remove ModelChecker::is_infeasible_ignoreRMW()

We don't make any special exceptions for this condition anymore, so drop
the function.

9 years agomodel: add immediate future value for RMW reordering
Brian Norris [Thu, 10 Jan 2013 01:39:24 +0000 (17:39 -0800)]
model: add immediate future value for RMW reordering

When RMW atomicity would otherwise rule an execution infeasible, we may
need to pass a future value back 'immediately,' to allow the
model-checker to effectively reorder the RMW's. For such cases, we don't
wait for all current promises to be resolved.

9 years agocyclegraph: detect cycles immediately
Brian Norris [Wed, 9 Jan 2013 23:26:47 +0000 (15:26 -0800)]
cyclegraph: detect cycles immediately

Previously, we have used a special case in CycleGraph to delay detection
of a mo-cycle (actually, an RMW atomicity violation) long enough so that
a RMW can "reorder" across another RMW by passing its future value.
Unfortunately, this only works some of the time, as the execution
*may or may not* be a feasible prefix which allows the sending of the
future value.

Instead, we need to pull this special case out of CycleGraph and (in
subsequent commits) will add a more proper solution in model.cc.

9 years agopromise: bugfix - a disabled thread should not be eliminated
Brian Norris [Thu, 24 Jan 2013 03:00:49 +0000 (19:00 -0800)]
promise: bugfix - a disabled thread should not be eliminated

Because we now only consider a subset of threads for satisfying
promises, we can have a disabled thread that still may satisfy a
promise; it could simply synchronize with another unrelated thread, then
continue to generate a write that can resolve the promise.

As a side effect, this change makes "has_failed()" much simpler.

9 years agomodel: modify promises on THREAD_{CREATE,FINISH}
Brian Norris [Thu, 24 Jan 2013 02:47:53 +0000 (18:47 -0800)]
model: modify promises on THREAD_{CREATE,FINISH}

When a thread is created it *must* pass its promise satisfiability to
its children.

When a thread finishes, we should remove it from all promises. This can
help prune a search early, if some read was depending only on the
finishing thread: we can then declare an unresolved promise.

9 years agopromise: associate Promises with a set of threads
Brian Norris [Thu, 24 Jan 2013 02:43:14 +0000 (18:43 -0800)]
promise: associate Promises with a set of threads

A Promise can be associated with a set of threads, so that we can
perform elimination more efficiently and precisely.

9 years agoaction: record future value
Brian Norris [Thu, 24 Jan 2013 02:05:28 +0000 (18:05 -0800)]
action: record future value

Future values don't currently show up in ModelAction (e.g., when
printing). We should set the value when we choose to read from a future

9 years agofuture_value: add thread ID parameter
Brian Norris [Thu, 24 Jan 2013 01:33:23 +0000 (17:33 -0800)]
future_value: add thread ID parameter

This just records the parameter for now, and makes it a distinction
between future values. Shouldn't affect model-checker behavior, except
for the introduction of extra future values: one for each thread which
writes the same value.

We calculate whether the writing thread exists at the time of the future
value and if not, find an ancestor thread which does.

9 years agonodestack: pass 'struct future_value' to add_future_value()
Brian Norris [Thu, 24 Jan 2013 01:24:11 +0000 (17:24 -0800)]
nodestack: pass 'struct future_value' to add_future_value()

This makes more sense than passing individual parameters. This way, we
construct our future_value in ModelChecker, then simply pass it to the

9 years agomodel: add const to get_thread(ModelAction *act)
Brian Norris [Thu, 24 Jan 2013 01:21:19 +0000 (17:21 -0800)]
model: add const to get_thread(ModelAction *act)

9 years agomodel: fixup indentation, spelling in comment
Brian Norris [Thu, 24 Jan 2013 01:02:46 +0000 (17:02 -0800)]
model: fixup indentation, spelling in comment

9 years agomodel: style
Brian Norris [Thu, 24 Jan 2013 00:51:39 +0000 (16:51 -0800)]
model: style

9 years agomodel: remove local variable
Brian Norris [Thu, 24 Jan 2013 00:34:00 +0000 (16:34 -0800)]
model: remove local variable

9 years agopromise: SnapshotAlloc for vector
Brian Norris [Wed, 23 Jan 2013 20:56:01 +0000 (12:56 -0800)]
promise: SnapshotAlloc for vector

We must ensure that any new memory allocated by the model-checker uses
our private snapshotting heap, not the user program's heap.

9 years agopromise: refactor has_failed()
Brian Norris [Wed, 23 Jan 2013 20:50:57 +0000 (12:50 -0800)]
promise: refactor has_failed()

has_failed() can simply call the thread_is_eliminated() function which
does much of the same computation already. We can drop the
'((int)i != promise_tid)' clause, since the 'promise_tid' thread must
already be eliminated.

9 years agopromise: move thread_is_eliminated()
Brian Norris [Wed, 23 Jan 2013 20:49:01 +0000 (12:49 -0800)]
promise: move thread_is_eliminated()

Should be in the implementation file, not the header.

9 years agopromise: rename has_sync_thread() -> thread_is_eliminated()
Brian Norris [Wed, 23 Jan 2013 20:36:28 +0000 (12:36 -0800)]
promise: rename has_sync_thread() -> thread_is_eliminated()

This function doesn't actually check for synchronization; there are
numerous ways to be eliminated.

9 years agopromise: rename check_promise() -> has_failed()
Brian Norris [Wed, 23 Jan 2013 19:53:33 +0000 (11:53 -0800)]
promise: rename check_promise() -> has_failed()

The name "check_promise" doesn't really tell what this function is
doing. It is actually checking if the promise is unresolvable.

9 years agopromise: refactor eliminate_thread()/check_promise()
Brian Norris [Wed, 23 Jan 2013 19:49:01 +0000 (11:49 -0800)]
promise: refactor eliminate_thread()/check_promise()

eliminate_thread() and check_promise() have near-duplicate code, for
checking if the promise has failed. This change makes them consistent
(check_promise() now knows to eliminate its own thread immediately) and
allows one function to simply call the other.

9 years agopromise: rename increment_threads() -> eliminate_thread()
Brian Norris [Wed, 23 Jan 2013 19:38:43 +0000 (11:38 -0800)]
promise: rename increment_threads() -> eliminate_thread()

This function name really doesn't describe what it does, in my opinion.
Update the name and add a description.

9 years agonodestack: add const
Brian Norris [Wed, 23 Jan 2013 19:10:20 +0000 (11:10 -0800)]
nodestack: add const

9 years agopromise: construct with a 'future_value' struct
Brian Norris [Wed, 23 Jan 2013 19:04:59 +0000 (11:04 -0800)]
promise: construct with a 'future_value' struct

Don't pass a bunch of parameters individually; just pass the struct.

9 years agonodestack/promise: move future_value struct, update headers
Brian Norris [Wed, 23 Jan 2013 19:02:38 +0000 (11:02 -0800)]
nodestack/promise: move future_value struct, update headers

struct future_value will be used more closely with class Promise, so put
it in the promise.h header. This requires some updates to other header

9 years agonodestack: pass writer ModelAction to add_future_value()
Brian Norris [Wed, 23 Jan 2013 18:43:48 +0000 (10:43 -0800)]
nodestack: pass writer ModelAction to add_future_value()

NodeStack will have to know a little more about who wrote the future
value, so just pass the ModelAction as a parameter.

9 years agonodestack: eliminate get_future_value_expiration()
Brian Norris [Wed, 23 Jan 2013 18:41:23 +0000 (10:41 -0800)]
nodestack: eliminate get_future_value_expiration()

We don't need separate accessors for each member of 'struct
future_value'. Just pass the entire struct.

9 years agonodestack: remove extra blank lines
Brian Norris [Wed, 23 Jan 2013 18:30:46 +0000 (10:30 -0800)]
nodestack: remove extra blank lines

9 years agoremove #include <list>
Brian Norris [Wed, 23 Jan 2013 18:17:44 +0000 (10:17 -0800)]
remove #include <list>

STL lists aren't used here anymore.

9 years agonodestack: improve debug print() method
Brian Norris [Wed, 23 Jan 2013 00:49:11 +0000 (16:49 -0800)]
nodestack: improve debug print() method

Print the contents of the future values and may-read-from set, if we're
printing the NodeStack for debugging purposes.

9 years agofix bug in promise handling code...
Brian Demsky [Wed, 23 Jan 2013 00:31:16 +0000 (16:31 -0800)]
fix bug in promise handling code...

if any promise for a thread resolved, we assumed that the corresponding
write happened after all promises for that threads...clearly doesn't
need to be the case...

[Brian Norris:] This fixes some bugs where we don't see all the expected
behaviors: e.g., with

  ./run.sh test/rmwprog.o -- 3

Now we see all 20 behaviors.

9 years agopromise: fixup style
Brian Norris [Wed, 23 Jan 2013 00:24:44 +0000 (16:24 -0800)]
promise: fixup style

9 years agotest: rmwprog: support command-line argument
Brian Norris [Tue, 22 Jan 2013 19:08:06 +0000 (11:08 -0800)]
test: rmwprog: support command-line argument

This test can easily be extended to allow more than 2 atomic increments
per thread. For instance, it's interesting to see the model-checker
behavior for 4 increments per thread. Now, you can do this with a simple
numeric command-line argument that gets passed to the user program.

Example - run rmwprog with 4 increments per thread, viewing the
execution traces verbosely:

  ./run.sh test/rmwprog.o -v -- 4

9 years agonodestack: improve debug prints
Brian Norris [Sat, 19 Jan 2013 00:43:02 +0000 (16:43 -0800)]
nodestack: improve debug prints

9 years agoschedule: improve scheduler printing
Brian Norris [Sat, 19 Jan 2013 00:38:55 +0000 (16:38 -0800)]
schedule: improve scheduler printing

Print more detailed, informative info about the Scheduler, still on a
single line.

9 years agoschedule: allow Schedule::print() even in non-DEBUG build
Brian Norris [Sat, 19 Jan 2013 00:30:26 +0000 (16:30 -0800)]
schedule: allow Schedule::print() even in non-DEBUG build

For instance, printing from w/in gdb

9 years agomodel: bugfix - sleep sets are NOT directly compatible with DPOR
Brian Norris [Thu, 17 Jan 2013 01:42:57 +0000 (17:42 -0800)]
model: bugfix - sleep sets are NOT directly compatible with DPOR

We failed to incorporate changes from the POPL'05 DPOR paper's addendum,
preventing us from seeing all behaviors in some test programs. This
fixes that.

9 years agolitmus: iriw: allow command-line switch 's' for seq_cst
Brian Norris [Wed, 16 Jan 2013 08:24:48 +0000 (00:24 -0800)]
litmus: iriw: allow command-line switch 's' for seq_cst

The IRIW litmus test fails if we make it seq_cst; we don't see all 15
potential behaviors. Run with:

  # release/acquire litmus test
  ./run.sh test/litmus/iriw.o -v

  # seq_cst litmus test
  ./run.sh test/litmus/iriw.o -v -- s

9 years agolitmus: iriw: use release/acquire, not release/relaxed
Brian Norris [Wed, 16 Jan 2013 07:57:45 +0000 (23:57 -0800)]
litmus: iriw: use release/acquire, not release/relaxed

9 years agotests: litmus: link up Makefile properly
Brian Norris [Wed, 16 Jan 2013 07:43:44 +0000 (23:43 -0800)]
tests: litmus: link up Makefile properly

Now this builds the litmus tests properly.

9 years agotest: litmus: add litmus tests from Nitpicking C++
Brian Norris [Tue, 15 Jan 2013 20:44:47 +0000 (12:44 -0800)]
test: litmus: add litmus tests from Nitpicking C++

This adds most of the litmus tests from Nitpicking C++ Concurrency. Note
that it leaves out the 'consume' tests (replacing it with the
also-mentioned release/acquire test). It doesn't test the seq_cst
results, although I could provide command-line switches to do so...

9 years agotest: Makefile: add $(BASE) variable
Brian Norris [Tue, 15 Jan 2013 20:30:33 +0000 (12:30 -0800)]
test: Makefile: add $(BASE) variable

Makes this Makefile a little more flexible

9 years agomodel: reformat execution trace prints
Brian Norris [Thu, 10 Jan 2013 18:54:02 +0000 (10:54 -0800)]
model: reformat execution trace prints

Bring the "INFEASIBLE" message together with the "Execution #" message,
to make the log more compact and readable (e.g., grep for "Execution"
will give you some regularly-patterned, useful information).

9 years agomodel: spelling mistake
Brian Norris [Thu, 10 Jan 2013 01:50:57 +0000 (17:50 -0800)]
model: spelling mistake

9 years agomodel: fixup "infeasible" messages
Brian Norris [Wed, 9 Jan 2013 23:54:04 +0000 (15:54 -0800)]
model: fixup "infeasible" messages

These messages should be much more compact and targeted. Currently, we
either get no infeasibility messages (when verbose=0) or we get messages
every time is_infeasible() is executed. Neither is helpful for debugging,
since the infeasibility may be temporary, as we choose a new path for
execution on the fly. So instead, just print the infeasibility message
at the end of infeasible executions.

Also, rather than spread the messages across multiple lines, just put
them together into a single string.

9 years agocyclegraph: add documentation
Brian Norris [Wed, 9 Jan 2013 22:07:07 +0000 (14:07 -0800)]
cyclegraph: add documentation

9 years agocyclegraph: remove redundant code
Brian Norris [Wed, 9 Jan 2013 21:47:57 +0000 (13:47 -0800)]
cyclegraph: remove redundant code

The edgeCreatesCycle() function can simply be reduced to
checkReachable(), since checkReachable() will detect "to == from".

9 years agocyclegraph: add edgeCreatesCycle() function
Brian Norris [Wed, 9 Jan 2013 00:40:29 +0000 (16:40 -0800)]
cyclegraph: add edgeCreatesCycle() function

This is repeated code, so make it a function.

9 years agocyclegraph: add const
Brian Norris [Wed, 9 Jan 2013 00:29:17 +0000 (16:29 -0800)]
cyclegraph: add const

9 years agomodel: add 'add_future_value()' wrapper
Brian Norris [Tue, 8 Jan 2013 02:22:57 +0000 (18:22 -0800)]
model: add 'add_future_value()' wrapper

Encapsulate a little logic in a function here, so we can reuse this in
other places.

9 years agomodel: add PendingFutureValue constructor
Brian Norris [Tue, 8 Jan 2013 01:38:25 +0000 (17:38 -0800)]
model: add PendingFutureValue constructor

9 years agonew test case
Brian Demsky [Tue, 8 Jan 2013 00:55:00 +0000 (16:55 -0800)]
new test case

9 years agocyclegraph: add back edges to CycleNode
Brian Norris [Fri, 4 Jan 2013 19:05:10 +0000 (11:05 -0800)]
cyclegraph: add back edges to CycleNode

9 years agohashtable: style
Brian Norris [Fri, 4 Jan 2013 18:09:29 +0000 (10:09 -0800)]
hashtable: style

9 years agocyclegraph: add putNode() helper
Brian Norris [Fri, 4 Jan 2013 17:53:04 +0000 (09:53 -0800)]
cyclegraph: add putNode() helper