var debugPoset … const uintSize … type bitset … func newBitset(n int) bitset { … } func (bs bitset) Reset() { … } func (bs bitset) Set(idx uint32) { … } func (bs bitset) Clear(idx uint32) { … } func (bs bitset) Test(idx uint32) bool { … } type undoType … const undoInvalid … const undoCheckpoint … const undoSetChl … const undoSetChr … const undoNonEqual … const undoNewNode … const undoAliasNode … const undoNewRoot … const undoChangeRoot … const undoMergeRoot … type posetUndo … const posetFlagUnsigned … type posetEdge … func newedge(t uint32, strict bool) posetEdge { … } func (e posetEdge) Target() uint32 { … } func (e posetEdge) Strict() bool { … } func (e posetEdge) String() string { … } type posetNode … type poset … func newPoset() *poset { … } func (po *poset) SetUnsigned(uns bool) { … } // Handle children func (po *poset) setchl(i uint32, l posetEdge) { … } func (po *poset) setchr(i uint32, r posetEdge) { … } func (po *poset) chl(i uint32) uint32 { … } func (po *poset) chr(i uint32) uint32 { … } func (po *poset) children(i uint32) (posetEdge, posetEdge) { … } // upush records a new undo step. It can be used for simple // undo passes that record up to one index and one edge. func (po *poset) upush(typ undoType, p uint32, e posetEdge) { … } // upushnew pushes an undo pass for a new node func (po *poset) upushnew(id ID, idx uint32) { … } // upushneq pushes a new undo pass for a nonequal relation func (po *poset) upushneq(idx1 uint32, idx2 uint32) { … } // upushalias pushes a new undo pass for aliasing two nodes func (po *poset) upushalias(id ID, i2 uint32) { … } // addchild adds i2 as direct child of i1. func (po *poset) addchild(i1, i2 uint32, strict bool) { … } // newnode allocates a new node bound to SSA value n. // If n is nil, this is an extra node (= only used internally). func (po *poset) newnode(n *Value) uint32 { … } // lookup searches for a SSA value into the forest of DAGS, and return its node. func (po *poset) lookup(n *Value) (uint32, bool) { … } // aliasnewnode records that a single node n2 (not in the poset yet) is an alias // of the master node n1. func (po *poset) aliasnewnode(n1, n2 *Value) { … } // aliasnodes records that all the nodes i2s are aliases of a single master node n1. // aliasnodes takes care of rearranging the DAG, changing references of parent/children // of nodes in i2s, so that they point to n1 instead. // Complexity is O(n) (with n being the total number of nodes in the poset, not just // the number of nodes being aliased). func (po *poset) aliasnodes(n1 *Value, i2s bitset) { … } func (po *poset) isroot(r uint32) bool { … } func (po *poset) changeroot(oldr, newr uint32) { … } func (po *poset) removeroot(r uint32) { … } // dfs performs a depth-first search within the DAG whose root is r. // f is the visit function called for each node; if it returns true, // the search is aborted and true is returned. The root node is // visited too. // If strict, ignore edges across a path until at least one // strict edge is found. For instance, for a chain A<=B<=C<D<=E<F, // a strict walk visits D,E,F. // If the visit ends, false is returned. func (po *poset) dfs(r uint32, strict bool, f func(i uint32) bool) bool { … } // Returns true if there is a path from i1 to i2. // If strict == true: if the function returns true, then i1 < i2. // If strict == false: if the function returns true, then i1 <= i2. // If the function returns false, no relation is known. func (po *poset) reaches(i1, i2 uint32, strict bool) bool { … } // findroot finds i's root, that is which DAG contains i. // Returns the root; if i is itself a root, it is returned. // Panic if i is not in any DAG. func (po *poset) findroot(i uint32) uint32 { … } // mergeroot merges two DAGs into one DAG by creating a new extra root func (po *poset) mergeroot(r1, r2 uint32) uint32 { … } // collapsepath marks n1 and n2 as equal and collapses as equal all // nodes across all paths between n1 and n2. If a strict edge is // found, the function does not modify the DAG and returns false. // Complexity is O(n). func (po *poset) collapsepath(n1, n2 *Value) bool { … } // findpaths is a recursive function that calculates all paths from cur to dst // and return them as a bitset (the index of a node is set in the bitset if // that node is on at least one path from cur to dst). // We do a DFS from cur (stopping going deep any time we reach dst, if ever), // and mark as part of the paths any node that has a children which is already // part of the path (or is dst itself). func (po *poset) findpaths(cur, dst uint32) bitset { … } func (po *poset) findpaths1(cur, dst uint32, seen bitset, path bitset) { … } // Check whether it is recorded that i1!=i2 func (po *poset) isnoneq(i1, i2 uint32) bool { … } // Record that i1!=i2 func (po *poset) setnoneq(n1, n2 *Value) { … } // CheckIntegrity verifies internal integrity of a poset. It is intended // for debugging purposes. func (po *poset) CheckIntegrity() { … } // CheckEmpty checks that a poset is completely empty. // It can be used for debugging purposes, as a poset is supposed to // be empty after it's fully rolled back through Undo. func (po *poset) CheckEmpty() error { … } // DotDump dumps the poset in graphviz format to file fn, with the specified title. func (po *poset) DotDump(fn string, title string) error { … } // Ordered reports whether n1<n2. It returns false either when it is // certain that n1<n2 is false, or if there is not enough information // to tell. // Complexity is O(n). func (po *poset) Ordered(n1, n2 *Value) bool { … } // OrderedOrEqual reports whether n1<=n2. It returns false either when it is // certain that n1<=n2 is false, or if there is not enough information // to tell. // Complexity is O(n). func (po *poset) OrderedOrEqual(n1, n2 *Value) bool { … } // Equal reports whether n1==n2. It returns false either when it is // certain that n1==n2 is false, or if there is not enough information // to tell. // Complexity is O(1). func (po *poset) Equal(n1, n2 *Value) bool { … } // NonEqual reports whether n1!=n2. It returns false either when it is // certain that n1!=n2 is false, or if there is not enough information // to tell. // Complexity is O(n) (because it internally calls Ordered to see if we // can infer n1!=n2 from n1<n2 or n2<n1). func (po *poset) NonEqual(n1, n2 *Value) bool { … } // setOrder records that n1<n2 or n1<=n2 (depending on strict). Returns false // if this is a contradiction. // Implements SetOrder() and SetOrderOrEqual() func (po *poset) setOrder(n1, n2 *Value, strict bool) bool { … } // SetOrder records that n1<n2. Returns false if this is a contradiction // Complexity is O(1) if n2 was never seen before, or O(n) otherwise. func (po *poset) SetOrder(n1, n2 *Value) bool { … } // SetOrderOrEqual records that n1<=n2. Returns false if this is a contradiction // Complexity is O(1) if n2 was never seen before, or O(n) otherwise. func (po *poset) SetOrderOrEqual(n1, n2 *Value) bool { … } // SetEqual records that n1==n2. Returns false if this is a contradiction // (that is, if it is already recorded that n1<n2 or n2<n1). // Complexity is O(1) if n2 was never seen before, or O(n) otherwise. func (po *poset) SetEqual(n1, n2 *Value) bool { … } // SetNonEqual records that n1!=n2. Returns false if this is a contradiction // (that is, if it is already recorded that n1==n2). // Complexity is O(n). func (po *poset) SetNonEqual(n1, n2 *Value) bool { … } // Checkpoint saves the current state of the DAG so that it's possible // to later undo this state. // Complexity is O(1). func (po *poset) Checkpoint() { … } // Undo restores the state of the poset to the previous checkpoint. // Complexity depends on the type of operations that were performed // since the last checkpoint; each Set* operation creates an undo // pass which Undo has to revert with a worst-case complexity of O(n). func (po *poset) Undo() { … }
Codebase Browser
go