1
use std::ffi::OsStr;
2
use std::fs::File;
3
use std::path::PathBuf;
4
use std::process::ExitCode;
5

            
6
use clap::Parser;
7
use clap::Subcommand;
8

            
9
use itertools::Itertools;
10
use merc_io::LargeFormatter;
11
use merc_ldd::Storage;
12
use merc_lts::AutStream;
13
use merc_lts::LtsBuilderMem;
14
use merc_lts::LtsFormat;
15
use merc_lts::guess_lts_format_from_extension;
16
use merc_lts::write_bcg;
17
use merc_symbolic::SymFormat;
18
use merc_symbolic::SymbolicLTS;
19
use merc_symbolic::SymbolicLtsBdd;
20
use merc_symbolic::convert_symbolic_lts;
21
use merc_symbolic::guess_format_from_extension;
22
use merc_symbolic::parse_compacted_dependency_graph;
23
use merc_symbolic::reachability;
24
use merc_symbolic::reachability_bdd;
25
use merc_symbolic::read_sylvan;
26
use merc_symbolic::read_symbolic_lts;
27
use merc_symbolic::reorder;
28
use merc_symbolic::sigref_symbolic;
29
use merc_tools::VerbosityFlag;
30
use merc_tools::Version;
31
use merc_tools::VersionFlag;
32
use merc_unsafety::print_allocator_metrics;
33
use merc_utilities::MercError;
34
use merc_utilities::Timing;
35
use which::which_in;
36

            
37
/// Default node capacity for the Oxidd decision diagram manager.
38
const DEFAULT_OXIDD_NODE_CAPACITY: usize = 2028;
39

            
40
/// A command line tool for symbolic labelled transition systems
41
#[derive(clap::Parser, Debug)]
42
#[command(arg_required_else_help = true)]
43
struct Cli {
44
    #[command(flatten)]
45
    version: VersionFlag,
46

            
47
    #[command(flatten)]
48
    verbosity: VerbosityFlag,
49

            
50
    #[command(subcommand)]
51
    commands: Option<Commands>,
52

            
53
    /// Number of workers for the Oxidd decision diagram manager.
54
    #[arg(long, global = true, default_value_t = 1)]
55
    oxidd_workers: u32,
56

            
57
    /// Node capacity for the Oxidd decision diagram manager.
58
    #[arg(long, global = true, default_value_t = DEFAULT_OXIDD_NODE_CAPACITY)]
59
    oxidd_node_capacity: usize,
60

            
61
    /// Cache capacity for the Oxidd decision diagram manager, if `None` it is set to the node capacity.
62
    #[arg(long, global = true)]
63
    oxidd_cache_capacity: Option<usize>,
64

            
65
    #[arg(long, global = true)]
66
    timings: bool,
67
}
68

            
69
/// Defines the subcommands for this tool.
70
#[derive(Debug, Subcommand)]
71
enum Commands {
72
    /// Print information related to the given symbolic LTS.
73
    Info(InfoArgs),
74
    /// Explore the given symbolic LTS.
75
    Explore(ExploreArgs),
76
    /// Computes a reordering for a dependency graph given by lpsreach or pbessolvesymbolic.
77
    Reorder(ReorderArgs),
78
    /// Convert a symbolic LTS to a concrete LTS.
79
    Convert(ConvertArgs),
80
    /// Apply reductions to a symbolic LTS.
81
    Reduce(ReduceArgs),
82
}
83

            
84
#[derive(clap::Args, Debug)]
85
struct InfoArgs {
86
    filename: PathBuf,
87

            
88
    /// Sets the input symbolic LTS format.
89
    #[arg(long)]
90
    format: Option<SymFormat>,
91
}
92

            
93
#[derive(clap::Args, Debug)]
94
struct ExploreArgs {
95
    filename: PathBuf,
96

            
97
    /// Sets the input symbolic LTS format.
98
    #[arg(long)]
99
    format: Option<SymFormat>,
100

            
101
    /// Use BDD based exploration by converting the symbolic LTS
102
    #[arg(long)]
103
    use_bdd: bool,
104

            
105
    /// Visualize intermediate BDDs using oxidd-vis.
106
    #[arg(long)]
107
    visualize: bool,
108
}
109

            
110
#[derive(clap::Args, Debug)]
111
struct ReorderArgs {
112
    /// Explicit path to the mCRL2 tools (lpsreach or pbessolvesymbolic)
113
    #[arg(long)]
114
    mcrl2_path: Option<PathBuf>,
115

            
116
    /// Explicit path to the kahypar tools
117
    #[arg(long)]
118
    kahypar_path: Option<PathBuf>,
119

            
120
    /// The input linear process specification file in the mCRL2 .lps format.
121
    filename: PathBuf,
122
}
123

            
124
#[derive(clap::Args, Debug)]
125
struct ConvertArgs {
126
    /// Sets the input symbolic LTS format.
127
    #[arg(long)]
128
    format: Option<SymFormat>,
129

            
130
    /// The input symbolic LTS file path.
131
    filename: PathBuf,
132

            
133
    /// Sets the output LTS format.
134
    #[arg(long)]
135
    output_format: Option<LtsFormat>,
136

            
137
    /// The output LTS file path.
138
    output: PathBuf,
139
}
140

            
141
#[derive(clap::Args, Debug)]
142
struct ReduceArgs {
143
    /// The input symbolic LTS file path.
144
    filename: PathBuf,
145

            
146
    /// Sets the input symbolic LTS format.
147
    #[arg(long)]
148
    format: Option<SymFormat>,
149

            
150
    /// Sets the output LTS format.
151
    #[arg(long)]
152
    output_format: Option<LtsFormat>,
153

            
154
    /// Visualize the reduction steps in oxidd-vis.
155
    #[arg(long)]
156
    visualize: bool,
157

            
158
    /// Split the signature per transition group.
159
    #[arg(long)]
160
    split_signature: bool,
161
}
162

            
163
/// Initializes the Oxidd BDD manager based on CLI arguments.
164
fn init_bdd_manager(cli: &Cli) -> oxidd::bdd::BDDManagerRef {
165
    oxidd::bdd::new_manager(
166
        cli.oxidd_node_capacity,
167
        cli.oxidd_cache_capacity.unwrap_or(cli.oxidd_node_capacity),
168
        cli.oxidd_workers,
169
    )
170
}
171

            
172
fn main() -> Result<ExitCode, MercError> {
173
    let cli = Cli::parse();
174

            
175
    env_logger::Builder::new()
176
        .filter_level(cli.verbosity.log_level_filter())
177
        .parse_default_env()
178
        .init();
179

            
180
    if cli.version.into() {
181
        eprintln!("{}", Version);
182
        return Ok(ExitCode::SUCCESS);
183
    }
184

            
185
    let timing = Timing::new();
186

            
187
    if let Some(command) = &cli.commands {
188
        match command {
189
            Commands::Info(args) => handle_info(args, &timing)?,
190
            Commands::Explore(args) => handle_explore(&cli, args, &timing)?,
191
            Commands::Reorder(args) => handle_reorder(args, &timing)?,
192
            Commands::Convert(args) => handle_convert(args, &timing)?,
193
            Commands::Reduce(args) => handle_reduce(&cli, args, &timing)?,
194
        }
195
    }
196

            
197
    if cli.timings {
198
        timing.print();
199
    }
200

            
201
    print_allocator_metrics();
202
    Ok(ExitCode::SUCCESS)
203
}
204

            
205
/// Reads the given symbolic LTS and prints information about it.
206
fn handle_info(args: &InfoArgs, timing: &Timing) -> Result<(), MercError> {
207
    let mut storage = Storage::new();
208

            
209
    let format = guess_format_from_extension(&args.filename, args.format)
210
        .ok_or("Cannot determine input symbolic LTS format")?;
211

            
212
    if format != SymFormat::Sym {
213
        return Err("Currently only the .sym format is supported for info".into());
214
    }
215

            
216
    let lts = timing.measure("read_symbolic_lts", || {
217
        read_symbolic_lts(&mut storage, File::open(&args.filename)?)
218
    })?;
219

            
220
    println!(
221
        "Number of states: {}",
222
        LargeFormatter(merc_ldd::len(&mut storage, lts.states()))
223
    );
224
    println!("Number of summand groups: {}", lts.transition_groups().len());
225

            
226
    Ok(())
227
}
228

            
229
/// Explores the given symbolic LTS.
230
fn handle_explore(cli: &Cli, args: &ExploreArgs, timing: &Timing) -> Result<(), MercError> {
231
    let mut storage = Storage::new();
232

            
233
    let format = guess_format_from_extension(&args.filename, args.format).ok_or("Cannot determine input format")?;
234

            
235
    let mut file = File::open(&args.filename)?;
236
    match format {
237
        SymFormat::Sylvan => {
238
            let lts = timing.measure("read_symbolic_lts", || read_sylvan(&mut storage, &mut file))?;
239
            explore_impl(&mut storage, cli, args, &lts, timing)?;
240
        }
241
        SymFormat::Sym => {
242
            let lts = timing.measure("read_symbolic_lts", || read_symbolic_lts(&mut storage, &mut file))?;
243
            explore_impl(&mut storage, cli, args, &lts, timing)?;
244
        }
245
    }
246

            
247
    Ok(())
248
}
249

            
250
fn explore_impl<L: SymbolicLTS>(
251
    storage: &mut Storage,
252
    cli: &Cli,
253
    args: &ExploreArgs,
254
    lts: &L,
255
    timing: &Timing,
256
) -> Result<(), MercError> {
257
    if args.use_bdd {
258
        let manager_ref = init_bdd_manager(cli);
259

            
260
        let lts_bdd = timing.measure("convert_bdd", || {
261
            SymbolicLtsBdd::from_symbolic_lts(storage, &manager_ref, lts)
262
        })?;
263

            
264
        println!(
265
            "LTS has {} states",
266
            timing.measure("explore_bdd", || reachability_bdd(
267
                &manager_ref,
268
                &lts_bdd,
269
                args.visualize
270
            ))?
271
        );
272
    } else {
273
        println!(
274
            "LTS has {} states",
275
            timing.measure("explore", || reachability(storage, lts))?
276
        );
277
    }
278
    Ok(())
279
}
280

            
281
/// Computes a variable reordering for the output of lpsreach.
282
fn handle_reorder(args: &ReorderArgs, _timing: &Timing) -> Result<(), MercError> {  
283
    // Find kahypar
284
    let kahypar_path = if let Some(path) = &args.kahypar_path {
285
        which_in("KaHyPar", Some(path), std::env::current_dir()?).map_err(|_e| "Cannot find KaHyPar")?
286
    } else {
287
        which::which("KaHyPar").map_err(|_e| "Cannot find KaHyPar in PATH")?
288
    };
289

            
290
    if args.filename.extension() == Some(OsStr::new("lps")) {
291
        // Find lpsreach
292
        let lpsreach_path = if let Some(path) = &args.mcrl2_path {
293
            which_in("lpsreach", Some(path), std::env::current_dir()?).map_err(|_e| "Cannot find lpsreach")?
294
        } else {
295
            which::which("lpsreach").map_err(|_e| "Cannot find lpsreach in PATH")?
296
        };
297

            
298
        // Run lpsreach with the --info flag to get dependency information
299
        let proc = duct::cmd!(lpsreach_path, "--info", &args.filename)
300
            .stdout_capture()
301
            .run()
302
            .map_err(|e| e.to_string())?;
303

            
304
        let graph = parse_compacted_dependency_graph(str::from_utf8(&proc.stdout)?);
305

            
306
        let order = reorder(&kahypar_path, &graph)?;
307
        println!("Computed variable order: {}", order.iter().format(" "));
308
    } else if args.filename.extension() == Some(OsStr::new("pbes")) {
309
        // Find pbessolvesymbolic
310
        let pbessolvesymbolic = if let Some(path) = &args.mcrl2_path {
311
            which_in("pbessolvesymbolic", Some(path), std::env::current_dir()?).map_err(|_e| "Cannot find pbessolvesymbolic")?
312
        } else {
313
            which::which("pbessolvesymbolic").map_err(|_e| "Cannot find pbessolvesymbolic in PATH")?
314
        };
315

            
316
        // Run pbessolvesymbolic with the --info flag to get dependency information
317
        let proc = duct::cmd!(pbessolvesymbolic, "--info", &args.filename)
318
            .stdout_capture()
319
            .run()
320
            .map_err(|e| e.to_string())?;
321

            
322
        let graph = parse_compacted_dependency_graph(str::from_utf8(&proc.stdout)?);
323
        let order = reorder(&kahypar_path, &graph)?;
324

            
325
        // Ensure that the first variable is 0 by removing it from order and printing it explicitly
326
        println!("Computed variable order: 0 {}", order.iter().filter(|&x| *x != 0).format(" "));
327
    } else {
328
        return Err("Input file must be either a .lps or .pbes file".into());
329
    }
330

            
331
    Ok(())
332
}
333

            
334
/// Converts a symbolic LTS to an explicit LTS.
335
fn handle_convert(args: &ConvertArgs, _timing: &Timing) -> Result<(), MercError> {
336
    let mut storage = Storage::new();
337

            
338
    let format =
339
        guess_format_from_extension(&args.filename, args.format).ok_or("Cannot determine input symbolic LTS format")?;
340
    if format != SymFormat::Sym {
341
        return Err("Currently only the .sym format is supported for conversion".into());
342
    }
343

            
344
    let mut file = File::open(&args.filename)?;
345
    let lts = read_symbolic_lts(&mut storage, &mut file)?;
346

            
347
    let output_format = guess_lts_format_from_extension(&args.output, args.output_format)
348
        .ok_or("Cannot determine output LTS format")?;
349

            
350
    match output_format {
351
        LtsFormat::Lts => {
352
            unimplemented!("Writing LTS format is not yet implemented");
353
        }
354
        LtsFormat::Aut => {
355
            let mut output = File::create(&args.output)?;
356
            let mut stream = AutStream::new(&mut output);
357
            convert_symbolic_lts(&mut storage, &mut stream, &lts)?;
358
        }
359
        LtsFormat::Bcg => {
360
            let explicit_lts =
361
                convert_symbolic_lts(&mut storage, &mut LtsBuilderMem::new(Vec::new(), Vec::new()), &lts)?;
362
            write_bcg(&explicit_lts, &args.output)?;
363
        }
364
    }
365

            
366
    Ok(())
367
}
368

            
369
/// Applies reductions to a symbolic LTS.
370
fn handle_reduce(cli: &Cli, args: &ReduceArgs, timing: &Timing) -> Result<(), MercError> {
371
    let format =
372
        guess_format_from_extension(&args.filename, args.format).ok_or("Cannot determine input symbolic LTS format")?;
373
    if format != SymFormat::Sym {
374
        return Err("Currently only the .sym format is supported for conversion".into());
375
    }
376

            
377
    let mut storage = Storage::new();
378
    let manager_ref = init_bdd_manager(cli);
379

            
380
    let mut file = File::open(&args.filename)?;
381
    let lts = read_symbolic_lts(&mut storage, &mut file)?;
382

            
383
    let lts_bdd = timing.measure("convert_bdd", || {
384
        SymbolicLtsBdd::from_symbolic_lts(&mut storage, &manager_ref, &lts)
385
    })?;
386

            
387
    timing.measure("reduction", || {
388
        sigref_symbolic(&manager_ref, &lts_bdd, timing, args.split_signature, args.visualize)
389
    })?;
390
    Ok(())
391
}