package frama-c

  1. Overview
  2. Docs
package frama-c
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Source file ranges.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
(**************************************************************************)
(*                                                                        *)
(*  This file is part of Frama-C.                                         *)
(*                                                                        *)
(*  Copyright (C) 2007-2024                                               *)
(*    CEA (Commissariat à l'énergie atomique et aux énergies              *)
(*         alternatives)                                                  *)
(*                                                                        *)
(*  you can redistribute it and/or modify it under the terms of the GNU   *)
(*  Lesser General Public License as published by the Free Software       *)
(*  Foundation, version 2.1.                                              *)
(*                                                                        *)
(*  It 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 Lesser General Public License for more details.                   *)
(*                                                                        *)
(*  See the GNU Lesser General Public License version 2.1                 *)
(*  for more details (enclosed in the file licenses/LGPLv2.1).            *)
(*                                                                        *)
(**************************************************************************)

let rec gcd a b =
  if a = 0 then abs b else
  if b = 0 then abs a else
    gcd b (a mod b)

let (%.) = gcd

(* -------------------------------------------------------------------------- *)
(* --- Range Maps                                                         --- *)
(* -------------------------------------------------------------------------- *)

type 'a range = {
  offset: int ;
  length: int ;
  data: 'a ;
}

let pp_range fmt r =
  Format.fprintf fmt "%04d..%04d" r.offset (r.offset + r.length - 1)

let pp_offset fmt r =
  Format.fprintf fmt "%04d:%04d" r.offset r.length

type 'a t = R of 'a range list (* sorted, no-overlap *)

let empty = R []

let singleton r =
  if not (0 <= r.offset && 0 < r.length) then
    raise (Invalid_argument "Region.Ranges.singleton") ;
  R [r]

let range ?(offset=0) ?(length=1) data = singleton { offset ; length ; data }

let rec find (k: int) = function
  | [] -> raise Not_found
  | ({ offset ; length } as r) :: rs ->
    if offset <= k && k <= offset + length then r else find k rs

let find k (R rs) = find k rs

let rec merge f ra rb =
  match ra, rb with
  | [], rs | rs, [] -> rs
  | a :: wa, b :: wb ->
    let a' = a.offset + a.length in
    let b' = b.offset + b.length in
    if a' <= b.offset then
      a :: merge f wa rb
    else
    if b' < a.offset then
      b :: merge f ra wb
    else
      let offset = min a.offset b.offset in
      let length = max a' b' - offset in
      let data = f a b in
      let r = { offset ; length ; data } in
      if a' < b'
      then merge f wa (r::wb)
      else merge f (r::wa) wb

let merge f (R x) (R y) = R (merge f x y)

let squash f = function
  | R [] -> None
  | R (x::xs) -> Some (List.fold_left (fun w r -> f w r.data) x.data xs)

let iteri f (R xs) = List.iter f xs
let iter f (R xs) = List.iter (fun r -> f r.data) xs
let map f (R xs) = R (List.map (fun r -> { r with data = f r.data }) xs)

(* -------------------------------------------------------------------------- *)
OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct