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
    Info(InfoArgs),
73
    Explore(ExploreArgs),
74
    Reorder(ReorderArgs),
75
    Convert(ConvertArgs),
76
    Reduce(ReduceArgs),
77
}
78

            
79
/// Print information related to the given symbolic LTS
80
#[derive(clap::Args, Debug)]
81
struct InfoArgs {
82
    filename: PathBuf,
83

            
84
    /// Sets the input symbolic LTS format.
85
    #[arg(long)]
86
    format: Option<SymFormat>,
87
}
88

            
89
/// Explore the given symbolic LTS
90
#[derive(clap::Args, Debug)]
91
struct ExploreArgs {
92
    filename: PathBuf,
93

            
94
    /// Sets the input symbolic LTS format.
95
    #[arg(long)]
96
    format: Option<SymFormat>,
97

            
98
    /// Use BDD based exploration by converting the symbolic LTS
99
    #[arg(long)]
100
    use_bdd: bool,
101

            
102
    /// Visualize intermediate BDDs using oxidd-vis.
103
    #[arg(long)]
104
    visualize: bool,
105
}
106

            
107
/// Computes a reordering for a dependency graph given by lpsreach or pbessolvesymbolic
108
#[derive(clap::Args, Debug)]
109
struct ReorderArgs {
110
    /// Path to the mCRL2 tools (lpsreach or pbessolvesymbolic)
111
    #[arg(long)]
112
    mcrl2_tool_path: Option<PathBuf>,
113

            
114
    /// The input linear process specification file in the mCRL2 .lps format.
115
    filename: PathBuf,
116
}
117

            
118
/// Convert a symbolic LTS to a concrete LTS
119
#[derive(clap::Args, Debug)]
120
struct ConvertArgs {
121
    /// Sets the input symbolic LTS format.
122
    #[arg(long)]
123
    format: Option<SymFormat>,
124

            
125
    /// The input symbolic LTS file path.
126
    filename: PathBuf,
127

            
128
    /// Sets the output LTS format.
129
    #[arg(long)]
130
    output_format: Option<LtsFormat>,
131

            
132
    /// The output LTS file path.
133
    output: PathBuf,
134
}
135

            
136
/// Apply reductions to a symbolic LTS
137
#[derive(clap::Args, Debug)]
138
struct ReduceArgs {
139
    /// The input symbolic LTS file path.
140
    filename: PathBuf,
141

            
142
    /// Sets the input symbolic LTS format.
143
    #[arg(long)]
144
    format: Option<SymFormat>,
145

            
146
    /// Sets the output LTS format.
147
    #[arg(long)]
148
    output_format: Option<LtsFormat>,
149

            
150
    /// Visualize the reduction steps in oxidd-vis.
151
    #[arg(long)]
152
    visualize: bool,
153
}
154

            
155
/// Initializes the Oxidd BDD manager based on CLI arguments.
156
fn init_bdd_manager(cli: &Cli) -> oxidd::bdd::BDDManagerRef {
157
    oxidd::bdd::new_manager(
158
        cli.oxidd_node_capacity,
159
        cli.oxidd_cache_capacity.unwrap_or(cli.oxidd_node_capacity),
160
        cli.oxidd_workers,
161
    )
162
}
163

            
164
fn main() -> Result<ExitCode, MercError> {
165
    let cli = Cli::parse();
166

            
167
    env_logger::Builder::new()
168
        .filter_level(cli.verbosity.log_level_filter())
169
        .parse_default_env()
170
        .init();
171

            
172
    if cli.version.into() {
173
        eprintln!("{}", Version);
174
        return Ok(ExitCode::SUCCESS);
175
    }
176

            
177
    let mut timing = Timing::new();
178

            
179
    if let Some(command) = &cli.commands {
180
        match command {
181
            Commands::Info(args) => handle_info(args, &mut timing)?,
182
            Commands::Explore(args) => handle_explore(&cli, args, &mut timing)?,
183
            Commands::Reorder(args) => handle_reorder(args, &mut timing)?,
184
            Commands::Convert(args) => handle_convert(args, &mut timing)?,
185
            Commands::Reduce(args) => handle_reduce(&cli, args, &mut timing)?,
186
        }
187
    }
188

            
189
    if cli.timings {
190
        timing.print();
191
    }
192

            
193
    print_allocator_metrics();
194
    Ok(ExitCode::SUCCESS)
195
}
196

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

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

            
203
    match format {
204
        SymFormat::Sylvan => {
205
            let lts = timing.measure("read_symbolic_lts", || -> Result<_, MercError> {
206
                read_sylvan(&mut storage, &mut File::open(&args.filename)?)
207
            })?;
208

            
209
            println!(
210
                "Number of states: {}",
211
                LargeFormatter(merc_ldd::len(&mut storage, lts.states()))
212
            );
213
            println!("Number of summand groups: {}", lts.transition_groups().len());
214
        }
215
        SymFormat::Sym => {
216
            let lts = timing.measure("read_symbolic_lts", || -> Result<_, MercError> {
217
                read_symbolic_lts(&mut storage, &mut 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
    }
227

            
228
    Ok(())
229
}
230

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

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

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

            
249
    Ok(())
250
}
251

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

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

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

            
283
/// Computes a variable reordering for the output of lpsreach.
284
fn handle_reorder(args: &ReorderArgs, _timing: &mut Timing) -> Result<(), MercError> {
285
    if args.filename.extension() == Some(OsStr::new("lps")) {
286
        // Find lpsreach
287
        let lpsreach_path = if let Some(path) = &args.mcrl2_tool_path {
288
            which_in("lpsreach", Some(path), std::env::current_dir()?)?
289
        } else {
290
            which::which("lpsreach").map_err(|_e| "Cannot find lpsreach in PATH")?
291
        };
292

            
293
        // Run lpsreach with the --info flag to get dependency information
294
        let proc = duct::cmd!(lpsreach_path, "--info", &args.filename)
295
            .stdout_capture()
296
            .run()
297
            .map_err(|e| e.to_string())?;
298

            
299
        let graph = parse_compacted_dependency_graph(str::from_utf8(&proc.stdout)?);
300

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

            
311
        // Run pbessolvesymbolic with the --info flag to get dependency information
312
        let proc = duct::cmd!(pbessolvesymbolic, "--info", &args.filename)
313
            .stdout_capture()
314
            .run()
315
            .map_err(|e| e.to_string())?;
316

            
317
        let graph = parse_compacted_dependency_graph(str::from_utf8(&proc.stdout)?);
318
        let mut order = reorder(&graph)?;
319

            
320
        // Ensure that the first variable is 0 by removing it and keeping the rest
321
        order.retain(|&x| x != 0);
322
        println!("Computed variable order: 0, {:?}", order);
323
    } else {
324
        return Err("Input file must be either a .lps or .pbes file".into());
325
    }
326

            
327
    Ok(())
328
}
329

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

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

            
340
    let mut file = File::open(&args.filename)?;
341
    let lts = read_symbolic_lts(&mut storage, &mut file)?;
342

            
343
    let output_format = guess_lts_format_from_extension(&args.output, args.output_format)
344
        .ok_or("Cannot determine output LTS format")?;
345

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

            
362
    Ok(())
363
}
364

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

            
373
    let mut storage = Storage::new();
374
    let manager_ref = init_bdd_manager(cli);
375

            
376
    let mut file = File::open(&args.filename)?;
377
    let lts = read_symbolic_lts(&mut storage, &mut file)?;
378

            
379
    let lts_bdd = timing.measure("convert_bdd", || {
380
        SymbolicLtsBdd::from_symbolic_lts(&mut storage, &manager_ref, &lts)
381
    })?;
382

            
383
    timing.measure("reduction", || sigref_symbolic(&manager_ref, &lts_bdd, timing, args.visualize))?;
384
    Ok(())
385
}