grew_fs.ml 12.2 KB
Newer Older
bguillaum's avatar
bguillaum committed
1
open Printf
pj2m's avatar
pj2m committed
2
open Log
bguillaum's avatar
bguillaum committed
3
4
5

open Grew_utils
open Grew_ast
pj2m's avatar
pj2m committed
6
7
8
9
10
11

module Feature = struct
  (* feature= (feature_name, disjunction of atomic values). empty list to encode "any value" *) 
  type t = 
    | Equal of string * string list
    | Different of string * string list
bguillaum's avatar
bguillaum committed
12
    | Param of string * int 
pj2m's avatar
pj2m committed
13

bguillaum's avatar
bguillaum committed
14
  let get_name = function | Equal (n,_) -> n | Different (n,_) | Param (n,_) -> n
pj2m's avatar
pj2m committed
15

16
17
  let get_atom = function | Equal (n,[one]) -> Some one | _ -> None

pj2m's avatar
pj2m committed
18
19
20
21
22
23
  let compare feat1 feat2 = Pervasives.compare (get_name feat1) (get_name feat2)
  (* suppose all feat_names to be different and ordered *)

  let rec check ?domain loc name values = match domain with
  | None -> ()
  | Some [] -> Log.fmessage "[GRS] Unknown feature name '%s' %s" name (Loc.to_string loc)
bguillaum's avatar
bguillaum committed
24
25
  | Some ((Ast.Open n)::_) when n = name -> ()
  | Some ((Ast.Closed (n,vs))::_) when n = name -> 
pj2m's avatar
pj2m committed
26
27
28
29
30
31
32
33
      (match List_.sort_diff values vs with 
      | [] -> ()
      | l -> Error.build ~loc "Unknown feature values '%s' for feature name '%s'" 
	    (List_.to_string (fun x->x) ", " l)
	    name
      )
  | Some (_::t) -> check ~domain:t loc name values

bguillaum's avatar
bguillaum committed
34
35
  let build ?pat_vars ?domain = function
    | ({Ast.kind=Ast.Equality unsorted_values ;name=name},loc) ->
pj2m's avatar
pj2m committed
36
37
38
	let values = List.sort Pervasives.compare unsorted_values in
	check ?domain loc name values;
	Equal (name, values)
bguillaum's avatar
bguillaum committed
39
    | ({Ast.kind=Ast.Disequality unsorted_values;name=name},loc) ->
pj2m's avatar
pj2m committed
40
41
42
	let values = List.sort Pervasives.compare unsorted_values in
	check ?domain loc name values;
	Different (name, values)
bguillaum's avatar
bguillaum committed
43
44
45
46
47
48
49
    | ({Ast.kind=Ast.Param var; name=name},loc) ->
        match pat_vars with
        | None -> Error.build "Unknown pattern variable '%s'" var
        | Some l -> 
            match List_.pos var l with
            | Some index -> Param (name, index)
            | None -> Error.build "Unknown pattern variable '%s'" var
pj2m's avatar
pj2m committed
50
51
52
53
54
end

module Feature_structure = struct
  (* list are supposed to be striclty ordered wrt compare*)
  type t = Feature.t list
bguillaum's avatar
bguillaum committed
55

bguillaum's avatar
bguillaum committed
56
57
  let build ?pat_vars ?domain ast_fs =
    let unsorted = List.map (Feature.build ?pat_vars ?domain) ast_fs in
pj2m's avatar
pj2m committed
58
    List.sort Feature.compare unsorted 
bguillaum's avatar
bguillaum committed
59
60
61
62

  let of_conll line =
    let morph_fs =
      List.map (fun (feat_name, feat_value) -> Feature.Equal (feat_name, [feat_value])) line.Conll.morph in
63
64
65
66
67
68
69
70
    let unsorted = 
      Feature.Equal ("phon", [line.Conll.phon]) ::
      Feature.Equal ("lemma", [line.Conll.lemma]) ::
      Feature.Equal ("cat", [line.Conll.pos2]) :: 
      morph_fs in
    List.sort Feature.compare unsorted 


pj2m's avatar
pj2m committed
71
72
73
  let empty = []

  let rec get name = function
bguillaum's avatar
bguillaum committed
74
75
    | [] -> None
    | Feature.Equal (n,l) :: _ when n=name -> Some l
pj2m's avatar
pj2m committed
76
    | Feature.Equal (n,l) :: t when n<name -> get name t
bguillaum's avatar
bguillaum committed
77
78
    | Feature.Equal _ :: _ -> None
    | Feature.Different _ :: _ -> Log.critical "[Feature_structure.get] this fs contains 'Different' constructor"
bguillaum's avatar
bguillaum committed
79
    | Feature.Param _ :: _ -> Log.critical "[Feature_structure.get] this fs contains 'Param' constructor"
pj2m's avatar
pj2m committed
80

bguillaum's avatar
bguillaum committed
81
82
  let get_atom name t =
    match get name t with
bguillaum's avatar
bguillaum committed
83
    | Some [one] -> Some one
bguillaum's avatar
bguillaum committed
84
85
    | _ -> None

pj2m's avatar
pj2m committed
86
87
  let string_of_feature = function
    | Feature.Equal (feat_name, atoms) -> 
bguillaum's avatar
bguillaum committed
88
	sprintf "%s=%s" feat_name
pj2m's avatar
pj2m committed
89
90
91
92
93
	  (match atoms with
	  | [] -> "*"
	  | h::t -> List.fold_right (fun atom acc -> atom^"|"^acc) t h
	  )
    | Feature.Different (feat_name, atoms) -> 
bguillaum's avatar
bguillaum committed
94
	sprintf "%s<>%s" feat_name
pj2m's avatar
pj2m committed
95
96
97
98
	  (match atoms with
	  | [] -> "EMPTY"
	  | h::t -> List.fold_right (fun atom acc -> atom^"|"^acc) t h
	  )
bguillaum's avatar
bguillaum committed
99
100
    | Feature.Param (feat_name, index) -> 
        sprintf "@%d" index
pj2m's avatar
pj2m committed
101
102
103

  let to_string t = List_.to_string string_of_feature "\\n" t

104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

  let get_main ?main_feat t =
    let main_list = match main_feat with
    | None -> []
    | Some string -> Str.split (Str.regexp " *; *") string in
    
    let rec loop = function
      | [] -> (None, t)
      | feat_name :: tail ->
          (match List.partition (fun f -> Feature.get_name f = feat_name) t with
          | ([], _) -> loop tail
          | ([one], sub) -> (Some one, sub)
          | _ -> Log.critical "[Feature_structure.to_dep] several feature with the same name") in
    loop main_list
    
  let escape  string =
    Str.global_replace (Str.regexp_string  "//PV//") ";"
      (Str.global_replace (Str.regexp_string  "//AND//") "&amp;" string)
  
  let to_dot ?main_feat t =
    let (main_opt, sub) = get_main ?main_feat t in
    sprintf "%s%s"
      (match main_opt with 
      | Some feat -> escape (match Feature.get_atom feat with Some atom -> atom^"|" | None -> "")
      | None -> "" )
      (List_.to_string string_of_feature "\\n" sub)

    
   


bguillaum's avatar
bguillaum committed
135
136
137
138
139
140
  let gr_of_feature = function
    | Feature.Equal (feat_name, [one]) -> sprintf "%s=\"%s\"" feat_name one
    | _ -> Log.critical "[Feature_structure.gr_of_feature] all feature in gr must be atomic value"

  let to_gr t = List_.to_string gr_of_feature ", " t

141
142
143
144
145
146
147
  let to_dep ?main_feat t =
    let (main_opt, sub) = get_main ?main_feat t in
    sprintf " word=\"%s\"; subword=\"%s\"; " 
      (match main_opt with 
      | Some feat -> escape (match Feature.get_atom feat with Some atom -> atom | None -> "")
      | None -> "")
      (escape (List_.to_string string_of_feature "#" sub))
pj2m's avatar
pj2m committed
148
149
150
151
152
153
154
155
156
157

  let rec set_feat feature_name atoms = function
    | [] -> [Feature.Equal (feature_name, atoms)]
    | ((Feature.Equal (fn,_))::_) as t when feature_name < fn -> (Feature.Equal (feature_name, atoms))::t
    | (Feature.Equal (fn,_))::t when feature_name = fn -> (Feature.Equal (feature_name, atoms))::t
    | Feature.Equal (fn,ats)::t -> Feature.Equal (fn,ats):: (set_feat feature_name atoms t) 
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2

  let rec del_feat feature_name = function
    | [] -> []
bguillaum's avatar
bguillaum committed
158
159
160
    | ((Feature.Equal (fn,_))::_) as t when feature_name < fn -> t
    | (Feature.Equal (fn,_))::t when feature_name = fn -> t
    | Feature.Equal (fn,ats)::t -> Feature.Equal (fn,ats):: (del_feat feature_name t) 
pj2m's avatar
pj2m committed
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2

  let compatible pattern fs =
    let rec loop = function
      | [], _ -> true

      (* Three next cases: each feature_name present in pattern must be in instance *)
      | _, [] -> false
      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> false
      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> false

      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop ((Feature.Equal (fn_pat, fv_pat))::t_pat, t)

      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop ((Feature.Different (fn_pat, fv_pat))::t_pat, t)

      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
181
182
	  (* when fn_pat = fn *) ->
            (match fv_pat, fv with 
pj2m's avatar
pj2m committed
183
184
185
186
187
188
189
	    | [],_ | _, [] -> loop (t_pat,t)
	    | l_pat,l -> not (List_.sort_disjoint l_pat l) && loop (t_pat,t)
	    )

      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	  (* when fn_pat = fn*) ->
 	  (match fv_pat, fv with 
bguillaum's avatar
bguillaum committed
190
	  | [],_ | _, [] -> loop (t_pat,t)  (* FIXME should be "false" *)
pj2m's avatar
pj2m committed
191
192
193
194
	  | l_pat,l -> (List_.sort_disjoint l_pat l) && loop (t_pat,t)
	  )
    | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2
    in loop (pattern,fs)
195
      
pj2m's avatar
pj2m committed
196

bguillaum's avatar
bguillaum committed
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
  let compatible_param param pattern fs =
    let rec loop acc_param = function
      | [], _ -> acc_param

      (* Three next cases: each feature_name present in pattern must be in instance: [] means unif failure *)
      | _, [] -> []
      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> []
      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) when fn_pat < fn -> []

      (* Two next cases: a feature in graph, not in pattern *) 
      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop acc_param ((Feature.Equal (fn_pat, fv_pat))::t_pat, t)
      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop acc_param ((Feature.Different (fn_pat, fv_pat))::t_pat, t)
      | ((Feature.Param (fn_pat, i))::t_pat, (Feature.Equal (fn, fv))::t) 
	when fn_pat > fn ->
	  loop acc_param ((Feature.Param (fn_pat, i))::t_pat, t)

      | ((Feature.Equal (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	  (* when fn_pat = fn *) ->
            (match fv_pat, fv with 
	    | [],_ -> (* pattern_value is ? *) loop acc_param (t_pat,t)
	    | l_pat,l when not (List_.sort_disjoint l_pat l) -> loop acc_param (t_pat,t)
            | _ -> (* l_pat and l disjoint -> no sol *) []
	    )

      | ((Feature.Different (fn_pat, fv_pat))::t_pat, (Feature.Equal (fn, fv))::t) 
	  (* when fn_pat = fn*) ->
 	    (match fv_pat, fv with 
	    | [],_ -> []
	    | l_pat,l when List_.sort_disjoint l_pat l -> loop acc_param (t_pat,t)
            | _ -> (* l_pat and l disjoint -> no disjoint *) []
	    )

      | ((Feature.Param (fn_pat, i))::t_pat, (Feature.Equal (fn, fv))::t)
          (* when fn_pat = fn*) ->
 	    (match fv with
	    | [atom] -> 
                let reduce_param = List.filter (fun (x,_) -> List.nth x i = atom) acc_param in
                loop reduce_param (t_pat,t)
            | _ -> Log.critical "[compatible_param] Graph feature value not atomic"
	    )
      | _ -> Log.bug "[Feature_structure.set_feat]: Disequality not allowed in graph features"; exit 2
    in loop param (pattern,fs)



pj2m's avatar
pj2m committed
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
  exception Fail_unif 
  exception Bug_unif of string 
  let unif fs1 fs2 = 
    let rec loop = function
      | [], fs 
      | fs, [] -> fs

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> f1 :: loop (t1, f2::t2)
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> f2 :: loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> raise Fail_unif
	  | fv -> (Feature.Equal (fn, fv)) :: (loop (t1, t2)))

       | _ -> raise (Bug_unif "two value declared \"Feature.Different\", cannot reply without the domain !")
    in try Some (loop (fs1, fs2)) with Fail_unif -> None




  let unifiable fs1 fs2 = 
    let rec loop = function
      | [], fs 
      | fs, [] -> true

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> loop (t1, f2::t2)
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))
	    
      | _ -> raise (Bug_unif "two value declared \"Different\", cannot reply without the domain !")
    in loop (fs1, fs2)



  let filter fs_p fs_g = 
    let rec loop = function
      | [], fs -> true
      | fs, [] -> false

      | (f1::t1, f2::t2) when Feature.compare f1 f2 < 0 -> false
      | (f1::t1, f2::t2) when Feature.compare f1 f2 > 0 -> loop (f1::t1, t2)

      (* all remaining case are fn1 = fn2 *)
      | ((Feature.Equal (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_inter fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Different (fn, fv1))::t1, (Feature.Equal (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv2 fv1 with
	  | [] -> false
	  | _ -> loop (t1, t2))

      | ((Feature.Equal (fn, fv1))::t1, (Feature.Different (_, fv2))::t2) -> 
 	  (match List_.sort_diff fv1 fv2 with
	  | [] -> false
	  | _ -> loop (t1, t2))
	    
      | _ -> raise (Bug_unif "two value declared \"Different\", cannot reply without the domain !")
    in loop (fs_p, fs_g)


end