132 lines
2.9 KiB
Go
132 lines
2.9 KiB
Go
/*
|
|
* This file is part of solvar. (https://git.redxen.eu/caskd/solvar)
|
|
* Copyright (c) 2022 Alex-David Denes
|
|
*
|
|
* solvar is free software: you can redistribute it and/or modify
|
|
* it under the terms of the GNU General Public License as published by
|
|
* the Free Software Foundation, either version 3 of the License, or
|
|
* any later version.
|
|
*
|
|
* solvar is distributed in the hope that it will be useful,
|
|
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
* GNU General Public License for more details.
|
|
*
|
|
* You should have received a copy of the GNU General Public License
|
|
* along with solvar. If not, see <https://www.gnu.org/licenses/>.
|
|
*/
|
|
|
|
package solvar
|
|
|
|
import (
|
|
"golang.org/x/exp/slices"
|
|
)
|
|
|
|
type Identifier string
|
|
|
|
type internalObject struct {
|
|
n, r []*Object
|
|
}
|
|
|
|
type Object struct {
|
|
Id []Identifier
|
|
Rel []Relation
|
|
}
|
|
|
|
type callbackSolver struct {
|
|
e error
|
|
io []*internalObject
|
|
}
|
|
|
|
func (oo internalObject) Copy() (no *internalObject) {
|
|
no = new(internalObject)
|
|
no.MergeRaw(oo)
|
|
return
|
|
}
|
|
|
|
func (o *internalObject) MergeRaw(m internalObject) {
|
|
o.n = append(o.n, m.n...)
|
|
o.r = append(o.r, m.r...)
|
|
return
|
|
}
|
|
|
|
func (d *DependencyGraph) solveObject(np *[]*Object, object *Object, rel RelationType, cb chan callbackSolver) {
|
|
var err error
|
|
var rio []*internalObject
|
|
|
|
// Setup deferred callback
|
|
defer func(e *error, i *[]*internalObject, cbc chan callbackSolver) {
|
|
cbc <- callbackSolver{e: *e, io: *i}
|
|
}(&err, &rio, cb)
|
|
|
|
p := make([]*Object, len(*np))
|
|
copy(p, *np)
|
|
p = append(p, object)
|
|
|
|
// Check if we already have visited the graph path
|
|
if !slices.Contains(p, object) {
|
|
// Fetch children and work on children if any
|
|
if rel == RelationTypeNeed {
|
|
lcb := make(chan callbackSolver, len(object.Rel))
|
|
for idxrel := range object.Rel {
|
|
go d.solveRelation(&p, &object.Rel[idxrel], lcb)
|
|
}
|
|
for range object.Rel {
|
|
cb := <-lcb
|
|
if cb.e != nil {
|
|
return
|
|
}
|
|
|
|
// Merge fetched elements with existing elements creating paths with all possible combinations
|
|
if len(rio) == 0 {
|
|
rio = cb.io
|
|
} else {
|
|
var tmp []*internalObject
|
|
for _, riov := range rio {
|
|
for _, cbv := range cb.io {
|
|
ob := riov.Copy()
|
|
ob.MergeRaw(*cbv)
|
|
tmp = append(tmp, ob)
|
|
}
|
|
}
|
|
rio = tmp
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// If no relations have been added or is reject, initialise empty object group
|
|
if rio == nil {
|
|
rio = append(rio, new(internalObject))
|
|
}
|
|
|
|
for _, rv := range rio {
|
|
// Relation list to append to
|
|
var rl *[]*Object
|
|
if rel == RelationTypeNeed {
|
|
rl = &rv.n
|
|
} else {
|
|
rl = &rv.r
|
|
}
|
|
|
|
*rl = append(*rl, object)
|
|
}
|
|
|
|
// Clean up invalid options
|
|
var tmp []*internalObject
|
|
for _, riov := range rio {
|
|
found := false
|
|
for _, n := range riov.n {
|
|
for _, r := range riov.r {
|
|
if r == n {
|
|
found = true
|
|
}
|
|
}
|
|
}
|
|
if !found {
|
|
tmp = append(tmp, riov)
|
|
}
|
|
}
|
|
rio = tmp
|
|
}
|