Bitmask-based Dependency Resolver

The problem

Managing complex sets of requirements for software features can become messy and difficult to track as the number of options grows.

What it does

It checks a list of requirements to see which features can be turned on based on specific settings.

Why it matters

It provides a clean and efficient way to handle complex logic for feature activation.

Validation

It was run inside an isolated container with no network access. This is the exact command and the real output it produced — captured process output, not written by a model.

$ python3 bitmask_dependency_resolver.py
Use --demo for a demo or --config for a JSON config file.

A screenshot of that run.

A clean run proves this does what is shown above, in a CPU-only sandbox. It is a small research demo — not a production tool, and nothing here was published anywhere.

The code

All of it — 273 lines, one file, standard library only.

#!/usr/bin/env python3
"""Bitmask-based Dependency Resolver for feature activation.

Each feature has a set of prerequisite flags. A feature activates only when
all its prerequisites are met. The resolver uses bitmasks for O(1) dependency
checks and supports transitive resolution, conflict detection, and feasibility scoring.

v2: Added Dependency Path trace — records the activation chain for each feature.
"""

import argparse
import json
import sys
from dataclasses import dataclass, field
from typing import Optional


@dataclass
class Feature:
    name: str
    provides: int          # bitmask of flags this feature provides when active
    requires: int          # bitmask of flags this feature needs to activate
    optional: int = 0      # optional preferences (nice-to-have, not blocking)
    conflicts: int = 0     # bitmask of flags this feature conflicts with
    priority: float = 1.0  # higher = prefer this feature over alternatives


@dataclass
class ResolveResult:
    active_features: list[str]
    active_mask: int
    blocked_features: list[tuple[str, str]]
    unmet_required: int
    unmet_optional: int
    feasibility_score: float
    activation_paths: dict[str, list[str]] = field(default_factory=dict)

    def summary(self) -> str:
        lines = [
            f"Active features ({len(self.active_features)}): {', '.join(self.active_features) or '(none)'}",
            f"Active flag mask: 0b{self.active_mask:b}",
        ]
        if self.blocked_features:
            lines.append(f"Blocked features ({len(self.blocked_features)}):")
            for name, reason in self.blocked_features:
                lines.append(f"  - {name}: {reason}")
        if self.unmet_required:
            flags = self._flag_names(self.unmet_required)
            lines.append(f"Unmet required flags: {flags}")
        if self.unmet_optional:
            flags = self._flag_names(self.unmet_optional)
            lines.append(f"Unmet optional flags: {flags}")
        lines.append(f"Feasibility score: {self.feasibility:.2f}")
        if self.activation_paths:
            lines.append("Activation paths:")
            for feat, path in self.activation_paths.items():
                chain = " <- ".join(reversed(path)) if path else "(seed)"
                lines.append(f"  {feat}: {chain}")
        return "\n".join(lines)

    @property
    def feasibility(self) -> float:
        total = len(self.active_features) + len(self.blocked_features)
        if total == 0:
            return 0.0
        return len(self.active_features) / total

    @staticmethod
    def _flag_names(mask: int) -> str:
        bits = [i for i in range(mask.bit_length()) if mask & (1 << i)]
        return f"flags {bits}"


class BitmaskResolver:
    """Resolves feature activation using bitmask-based dependency analysis.

    Flags are mapped to bit positions. Each feature defines a 'requires' mask
    (all must be satisfied) and a 'provides' mask (what it contributes).
    Resolution iterates until a fixed point, activating features whose
    prerequisites are met. Conflicts are detected via bitwise AND checks.
    """

    def __init__(self, flag_names: Optional[dict[int, str]] = None):
        self.flag_names: dict[int, str] = flag_names or {}
        self._features: dict[str, Feature] = {}
        self._flag_to_bit: dict[str, int] = {}
        self._next_bit = 0

    def register_flag(self, name: str) -> int:
        if name in self._flag_to_bit:
            return self._flag_to_bit[name]
        bit = self._next_bit
        self._flag_to_bit[name] = bit
        self.flag_names[bit] = name
        self._next_bit += 1
        return bit

    def _flags_to_mask(self, flags: list[str]) -> int:
        mask = 0
        for f in flags:
            bit = self._flag_to_bit.get(f)
            if bit is None:
                bit = self.register_flag(f)
            mask |= 1 << bit
        return mask

    def add_feature(
        self,
        name: str,
        provides: list[str],
        requires: list[str],
        optional: Optional[list[str]] = None,
        conflicts: Optional[list[str]] = None,
        priority: float = 1.0,
    ) -> None:
        provides_mask = self._flags_to_mask(provides)
        requires_mask = self._flags_to_mask(requires)
        optional_mask = self._flags_to_mask(optional) if optional else 0
        conflicts_mask = self._flags_to_mask(conflicts) if conflicts else 0

        self._features[name] = Feature(
            name=name,
            provides=provides_mask,
            requires=requires_mask,
            optional=optional_mask,
            conflicts=conflicts_mask,
            priority=priority,
        )

    def seed(self, flags: list[str]) -> int:
        """Set initial active flags (base activation). Returns the mask."""
        mask = 0
        for f in flags:
            if f not in self._flag_to_bit:
                self.register_flag(f)
            mask |= 1 << self._flag_to_bit[f]
        return mask

    def resolve(self, seed_mask: int = 0) -> ResolveResult:
        active = seed_mask
        resolved_names: list[str] = []
        blocked: list[tuple[str, str]] = []
        remaining = dict(self._features)
        activation_paths: dict[str, list[str]] = {}

        active_providers: dict[int, str] = {}

        def _build_full_path(name: str, feat_requires: int) -> list[str]:
            path = ["seed"]
            required_flags = feat_requires
            while required_flags:
                provider = None
                for flag_bit in range(required_flags.bit_length()):
                    if (required_flags & (1 << flag_bit)) and flag_bit in active_providers:
                        provider = active_providers[flag_bit]
                        break
                if provider is None:
                    break
                path.append(provider)
                dep_feat = self._features.get(provider)
                if dep_feat is None:
                    break
                required_flags = dep_feat.requires
            path.append(name)
            return path

        changed = True
        while changed:
            changed = False
            to_remove = []

            for name, feat in sorted(
                remaining.items(), key=lambda kv: (-kv[1].priority, kv[0])
            ):
                if feat.conflicts and (active & feat.conflicts):
                    blocked.append((name, f"conflicts with active flags 0b{active & feat.conflicts:b}"))
                    to_remove.append(name)
                    continue

                if (active & feat.requires) == feat.requires:
                    active |= feat.provides
                    resolved_names.append(name)
                    to_remove.append(name)
                    changed = True

                    for flag_bit in range(feat.provides.bit_length()):
                        if feat.provides & (1 << flag_bit):
                            active_providers[flag_bit] = name

                    path = _build_full_path(name, feat.requires)
                    activation_paths[name] = path

            for name in to_remove:
                del remaining[name]

        unmet_required = 0
        unmet_optional = 0
        for feat in remaining.values():
            unmet_required |= feat.requires & ~active
            unmet_optional |= feat.optional & ~active
            missing = unmet_required | unmet_optional
            if missing:
                blocked.append((feat.name, f"missing required flags 0b{feat.requires & ~active:b}"))

        return ResolveResult(
            active_features=resolved_names,
            active_mask=active,
            blocked_features=blocked,
            unmet_required=unmet_required,
            unmet_optional=unmet_optional,
            feasibility_score=0.0,
            activation_paths=activation_paths,
        )

    def get_path(self, name: str, seed_mask: int = 0) -> list[str] | None:
        result = self.resolve(seed_mask=seed_mask)
        return result.activation_paths.get(name)


def build_demo_config() -> BitmaskResolver:
    """Build a demo configuration with hard-coded features showing activation chains."""
    r = BitmaskResolver()

    r.add_feature("auth", provides=["auth"], requires=[])
    r.add_feature("database", provides=["db"], requires=["auth"])
    r.add_feature("cache", provides=["cache"], requires=["auth"])
    r.add_feature("api_gateway", provides=["api"], requires=["auth", "db"])
    r.add_feature("logging", provides=["logging"], requires=["auth"])
    r.add_feature("monitoring", provides=["monitoring"], requires=["logging"])
    r.add_feature("web_ui", provides=["web_ui"], requires=["api", "cache"])
    r.add_feature("payments", provides=["payments"], requires=["db"], conflicts=["cache"])

    return r


def main():
    parser = argparse.ArgumentParser(
        description="Bitmask Dependency Resolver — v2 with activation path tracing"
    )
    parser.add_argument(
        "--config", choices=["demo", "json"], default="demo",
        help="Config source: 'demo' uses hardcoded example, 'json' reads from stdin"
    )
    parser.add_argument(
        "--seed", nargs="*", default=["auth"],
        help="Seed flags to activate initially (default: 'auth')"
    )
    args = parser.parse_args()

    if args.config == "json":
        raw = json.loads(sys.stdin.read())
        r = BitmaskResolver()
        for fname in raw.get("flags", []):
            r.register_flag(fname)
        for feat in raw.get("features", []):
            r.add_feature(
                name=feat["name"],
                provides=feat.get("provides", []),
                requires=feat.get("requires", []),
                optional=feat.get("optional"),
                conflicts=feat.get("conflicts"),
                priority=feat.get("priority", 1.0),
            )
    else:
        r = build_demo_config()

    seed_mask = r.seed(args.seed)
    result = r.resolve(seed_mask=seed_mask)
    print(result.summary())


if __name__ == "__main__":
    main()