# mala1180/pps-22-satify architecture

> Architecture diagram of the GitHub repository mala1180/pps-22-satify, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-05-19). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/mala1180/pps-22-satify
- Repository: https://github.com/mala1180/pps-22-satify

## Overview

##### Project Type and Purpose
- Satify is a standalone, open-source, pure-functional SAT solver written in Scala 3.
- It provides:
- A DSL to express boolean formulas and classical problems (N-Queens, Graph Coloring, Nurse Scheduling).
- Two core algorithms: Tseitin transformation (formula → CNF) and DPLL search (CNF satisfiability).
- An MVU (Model-View-Update) architectural shell for interactive use (CLI/REPL style).

##### File-Structure Analysis
- Top-level: build files (`build.sbt`), CI/CD workflows (`.github/workflows`), docs (`doc/`), source (`src/`), tests (`src/test/`).
- `src/main/scala/satify`: four main packages:
- `dsl`: user-facing language constructs and conversions.
- `model`: domain types (Expression, CNF, Problems, Solver models, Errors).
- `update`: MVU “controller” layer broken into Parser, Converters, Solver implementations.
- `view`: UI components and rendering logic.
- `satify/app`: MVU orchestration (`Architecture.scala`, `Main.scala`).
- Resources: sample CNF files, images for the UI/logo.
- Tests mirror this structure using both unit and Cucumber-style feature tests.

##### Key README Insights
- Emphasis on immutability, declarative/api style, idiomatic Scala.
- Two main algorithms: Tseitin (CNF conversion) and DPLL (SAT search).
- DSL use cases and provided example problems.

1. Application Shell (satify.app.Main)
2. DSL Layer (satify.dsl)
3. Model Layer (satify.model)
4. Update Layer (satify.update)
– Parser (DimacsParser)
– Converters (TseitinTransformation)
– Solver (DPLL variants)
5. View Layer (satify.view)
6. External I/O (CLI or file inputs/outputs)

- User Input → Application Shell → DSL Layer (or → Parser for DIMACS)
- DSL Layer → Model Layer (builds Expression or Problem instances)
- Model Layer → Update Layer/Converters (generates CNF)
- Update Layer/Parser + Converters → Solver → Solution in Model Layer
- Model Layer (Solution/State) → View Layer → Console/UI Output

c. Architectural Patterns & Principles:
– MVU (Model-View-Update) in `satify.app`
– Functional pipelines: DSL → Model → Conversion → Solver → View
– Immutable data models (`case class`), pure functions (no mutable state)
– Separation of concerns by package: DSL, Domain, Controller, UI

d. Technologies & Frameworks:
– Scala 3.3.0, sbt 1.9.1, JDK 17
– Scala pattern matching for parser and converters
– Cucumber (via `src/test/resources/features`) for BDD tests
– No external UI framework (console-based view using Scala’s native libs)

##### Essential Elements
– Component labels & package names
– Notes on immutability and pure functions at the boundaries

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% External Systems
    subgraph "External I/O" 
        direction TB
        CLI["CLI Input/Output"]:::external
        Files["Resource Files (cnf/, img/)"]:::external
    end

    %% Application Shell
    Shell["satify.app.Main / Architecture"]:::package
    click Shell "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/app/Main.scala"
    click Shell "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/app/Architecture.scala"

    %% DSL Layer
    subgraph "DSL Layer" 
        direction TB
        DSL["DSL.scala"]:::package
        Convs["Conversions.scala"]:::package
        EncodingsDSL["Encodings.scala"]:::package
        Numbers["Numbers.scala"]:::package
        Operators["Operators.scala"]:::package
        Reflection["Reflection.scala"]:::package
    end
    click DSL "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/DSL.scala"
    click Convs "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/Conversions.scala"
    click EncodingsDSL "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/Encodings.scala"
    click Numbers "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/Numbers.scala"
    click Operators "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/Operators.scala"
    click Reflection "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/dsl/Reflection.scala"

    %% Model Layer
    subgraph "Model Layer"
        direction TB
        Solution["Solution.scala"]:::package
        State["State.scala"]:::package
        CNFModel["CNF.scala"]:::package
        Expr["Expression.scala"]:::package
        ExprEnc["Encodings.scala"]:::package
        SymGen["SymbolGeneration.scala"]:::package
        UtilsExpr["Utils.scala"]:::package
        Error["Error.scala"]:::package
        Problem["Problem.scala"]:::package
        GraphColor["GraphColoring.scala"]:::package
        NQueens["NQueens.scala"]:::package
        Nurse["NurseScheduling.scala"]:::package
        DecisionTree["DecisionTree.scala"]:::package
        OptionalVar["OptionalVariable.scala"]:::package
        PartialAssign["PartialAssignment.scala"]:::package
    end
    click Solution "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/Solution.scala"
    click State "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/State.scala"
    click CNFModel "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/cnf/CNF.scala"
    click Expr "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/expression/Expression.scala"
    click ExprEnc "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/expression/Encodings.scala"
    click SymGen "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/expression/SymbolGeneration.scala"
    click UtilsExpr "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/expression/Utils.scala"
    click Error "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/errors/Error.scala"
    click Problem "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/problems/Problem.scala"
    click GraphColor "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/problems/GraphColoring.scala"
    click NQueens "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/problems/NQueens.scala"
    click Nurse "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/problems/NurseScheduling.scala"
    click DecisionTree "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/solver/DecisionTree.scala"
    click OptionalVar "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/solver/OptionalVariable.scala"
    click PartialAssign "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/model/solver/PartialAssignment.scala"

    %% Update Layer
    subgraph "Update Layer"
        direction TB
        subgraph Parser
            P1["Parser.scala"]:::package
            P2["DimacsParser.scala"]:::package
        end
        subgraph Converters
            C1["Converter.scala"]:::package
            C2["ConverterType.scala"]:::package
            T1["TseitinTransformation.scala"]:::algo
            T2["Utils.scala"]:::package
        end
        subgraph Solver
            SAPI["Solver.scala"]:::package
            STYPE["SolverType.scala"]:::package
            subgraph DPLL
                D1["DpllDecision.scala"]:::algo
                D2["Optimizations.scala"]:::algo
                subgraph CNF Modules
                    CNF1["CNFSat.scala"]:::algo
                    CNF2["CNFSimplification.scala"]:::algo
                end
                subgraph Impl
                    DI1["DpllEnumerator.scala"]:::algo
                    DI2["DpllFinder.scala"]:::algo
                end
                DU["PartialAssignmentUtils.scala"]:::package
            end
        end
        M1["Message.scala"]:::package
        U1["Update.scala"]:::package
        U2["Utils.scala"]:::package
    end
    click P1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/parser/Parser.scala"
    click P2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/parser/DimacsParser.scala"
    click C1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/converters/Converter.scala"
    click C2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/converters/ConverterType.scala"
    click T1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/converters/tseitin/TseitinTransformation.scala"
    click T2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/converters/tseitin/Utils.scala"
    click SAPI "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/Solver.scala"
    click STYPE "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/SolverType.scala"
    click D1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/DpllDecision.scala"
    click D2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/Optimizations.scala"
    click CNF1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/cnf/CNFSat.scala"
    click CNF2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/cnf/CNFSimplification.scala"
    click DI1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/impl/DpllEnumerator.scala"
    click DI2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/impl/DpllFinder.scala"
    click DU "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/solver/dpll/utils/PartialAssignmentUtils.scala"
    click M1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/Message.scala"
    click U1 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/Update.scala"
    click U2 "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/update/Utils.scala"

    %% View Layer
    subgraph "View Layer"
        direction TB
        ViewCore["View.scala"]:::package
        Reactions["Reactions.scala"]:::package
        Components["Components.scala"]:::package
        Listeners["Listeners.scala"]:::package
        CompUtils["ComponentUtils.scala"]:::package
        Constants["Constants.scala"]:::package
        ProbTitle["ProblemTitle.scala"]:::package
        TextPane["TextPaneUtils.scala"]:::package
        Title["Title.scala"]:::package
    end
    click ViewCore "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/View.scala"
    click Reactions "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/Reactions.scala"
    click Components "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/components/Components.scala"
    click Listeners "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/components/Listeners.scala"
    click CompUtils "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/utils/ComponentUtils.scala"
    click Constants "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/utils/Constants.scala"
    click ProbTitle "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/utils/ProblemTitle.scala"
    click TextPane "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/utils/TextPaneUtils.scala"
    click Title "https://github.com/mala1180/pps-22-satify/blob/main/src/main/scala/satify/view/utils/Title.scala"

    %% Data Flows
    CLI -->|"user input"| Shell
    Files -->|"load CNF"| P2
    Shell -->|"parse DSL"| DSL
    Shell -->|"receive DIMACS"| P2
    DSL -->|"Expression/Problem"| Expr
    Expr -->|"to CNF"| C1
    P2 -->|"CNF"| CNFModel
    C1 -->|"CNF"| T1
    T1 -->|"CNF"| CNFModel
    CNFModel -->|"CNF"| SAPI
    SAPI -->|"solve CNF"| D1
    D1 -->|"Solution"| Solution
    Solution -->|"state"| State
    State -->|"view state"| ViewCore
    ViewCore -->|"render"| CLI

    %% Styles
    classDef package fill:#D6E9FE,stroke:#0366D6
    classDef external fill:#DFFFE0,stroke:#3C763D
    classDef algo fill:#FFE9A6,stroke:#B58900
```
