648
647
-define(TID, #qid{lcid = template, no = ?TNO}).
650
opt_info(TemplateInfo, Sizes, JoinInfo, ColumnConstants0, MSQs, L) ->
651
SzCls = [{clause,L,[?I(C)],[],[?I(Sz)]} || {C,Sz} <- sort(Sizes)]
649
opt_info(TemplateInfo, Sizes, JoinInfo, MSQs, L,
650
EqColumnConstants0, EqualColumnConstants0) ->
651
SzCls = [{clause,L,[?I(C)],[],[?I(Sz)]} || {C,Sz} <- lists:sort(Sizes)]
652
652
++ [{clause,L,[?V('_')],[],[?A(undefined)]}],
653
653
S = [{size, {'fun', L, {clauses, SzCls}}}],
654
654
J = case JoinInfo of [] -> []; _ -> [{join, abstr(JoinInfo, L)}] end,
655
655
%% Superfluous clauses may be emitted:
656
TCls0 = lists:append(
657
657
[[{clause,L,[abstr(Col, L),EqType],[],
658
658
[abstr(TemplCols, L)]} ||
659
659
{Col,TemplCols} <- TemplateColumns]
660
660
|| {EqType, TemplateColumns} <- TemplateInfo]),
661
TCls = sort(TCls0) ++ [{clause,L,[?V('_'),?V('_')],[],[{nil,L}]}],
661
TCls = lists:sort(TCls0) ++ [{clause,L,[?V('_'),?V('_')],[],[{nil,L}]}],
662
662
T = [{template, {'fun', L, {clauses, TCls}}}],
664
664
%% The template may also have a constant function (IdNo = 0).
665
665
%% Only constant template columns are interesting.
666
ColumnConstants = [CC || {{IdNo,_Col},Const,_FilNs}=CC <- ColumnConstants0,
667
(IdNo =/= ?TNO) or (length(Const) =:= 1)],
668
Ns = lists:usort([IdNo || {{IdNo,_Col},_Const,_FilNs} <- ColumnConstants]),
669
CCs = [{clause,L,[?I(IdNo)],[],[column_fun(ColumnConstants, IdNo, L)]}
671
++ [{clause,L,[?V('_')],[],[?A(no_column_fun)]}],
672
C = [{constants,{'fun',L,{clauses,CCs}}}],
674
ConstCols = [{IdNo,Col} || {{IdNo,Col},[_],_FilNs} <- ColumnConstants],
666
EqColumnConstants = opt_column_constants(EqColumnConstants0),
667
CCs = opt_constants(L, EqColumnConstants),
668
EqC = {constants,{'fun',L,{clauses,CCs}}},
670
EqualColumnConstants = opt_column_constants(EqualColumnConstants0),
671
ECCs = opt_constants(L, EqualColumnConstants),
672
EqualC = {equal_constants,{'fun',L,{clauses,ECCs}}},
673
C = [EqC | [EqualC || true <- [CCs =/= ECCs]]],
675
%% Comparisons yield more constant columns than matchings.
676
ConstCols = [{IdNo,Col} ||
677
{{IdNo,Col},[_],_FilNs} <- EqualColumnConstants],
675
678
ConstColsFamily = family_list(ConstCols),
676
679
NSortedCols0 = [{IdNo,hd(lists:seq(1, length(Cols)+1)--Cols)} ||
677
680
{IdNo,Cols} <- ConstColsFamily],
1016
1044
{FilterData, GeneratorData} = qual_data(Qualifiers),
1017
1045
{Filter, Anon1, Imported} =
1018
1046
filter_info(FilterData, AllIVs, Dependencies, State),
1019
BindFun = fun(Value, Op) -> is_bindable(Value, Op, Imported) end,
1047
PatBindFun = fun(_Op, Value) -> is_bindable(Value) end,
1020
1048
{PatternFrame, PatternVars} =
1021
pattern_frame(GeneratorData, BindFun, Anon1, State),
1022
SkipFun = fun(Fs) -> Fs end,
1049
pattern_frame(GeneratorData, PatBindFun, Anon1, State),
1023
1050
PatternFrames = frame2frames(PatternFrame),
1024
Fs = filter(Filter, PatternFrames, BindFun, SkipFun, State),
1026
Selector = fun(Value) -> is_const(Value, Imported) end,
1027
ColumnConstants0 = [frames_to_columns(Fs, PV, QId, Selector) ||
1028
{QId,PV} <- PatternVars],
1029
ColumnConstants1 = flatten(ColumnConstants0),
1053
filter(Filter, PatternFrames, BindFun, State, Imported)
1055
SzFs = FilterFun(PatBindFun),
1057
SizeInfo = pattern_sizes(PatternVars, SzFs),
1058
SelectorFun = const_selector(Imported),
1031
1059
PatternConstants =
1032
flatten([frames_to_columns(PatternFrames, PV, QId, Selector) ||
1033
{QId,PV} <- PatternVars]),
1035
family_list([{GId, {Col,Vals}} ||
1036
{{GId,Col},Vals} <- ColumnConstants1--PatternConstants,
1039
ColumnConstants = lu_skip(ColumnConstants1, FilterData, BindFun, Selector,
1040
PatternFrame, PatternVars, Dependencies, State),
1041
PatternSizes = [{QId#qid.no, Size} ||
1042
{QId,PV} <- PatternVars,
1043
undefined =/= (Size = pattern_size(Fs, PV))],
1044
{ColumnConstants, PatternSizes, ExtraConstants}.
1060
lists:flatten(frames_to_columns(PatternFrames, PatternVars,
1061
deref_pattern(Imported),
1062
SelectorFun, Imported,
1065
{EqColumnConstants, _EqExtraConsts} =
1066
constants(FilterFun, PatternVars, PatternConstants, PatternFrame,
1067
FilterData, Dependencies, _LookupOp1 = '=:=',
1069
{EqualColumnConstants, EqualExtraConsts} =
1070
constants(FilterFun, PatternVars, PatternConstants, PatternFrame,
1071
FilterData, Dependencies, _LookupOp2 = '==',
1074
%% Use compared extra constants only because:
1075
%% - merge join compares terms;
1076
%% - the constants from the matching unification is a subset of the
1077
%% constants from the comparing unification.
1078
%% Using constants from the matching unification would make it
1079
%% possible to skip some (more) objects when joining.
1081
[{{GId,Col},{Val,Op}} ||
1082
{Consts,Op} <- [{EqualExtraConsts,'=='}],
1083
{{GId,Col},Val} <- Consts],
1085
family_list([{GId, {Col,ValOps}} ||
1086
{{GId,Col},ValOps} <- family_list(ExtraCon1)]),
1087
{EqColumnConstants, EqualColumnConstants, ExtraConstants, SizeInfo}.
1089
constants(FilterFun, PatternVars, PatternConstants, PatternFrame,
1090
FilterData, Dependencies, LookupOp, Imported, State) ->
1091
BindFun = fun(_Op, Value) -> is_bindable(Value) end,
1092
Fs = FilterFun(BindFun),
1093
SelectorFun = const_selector(Imported),
1094
ColumnConstants0 = frames_to_columns(Fs, PatternVars,
1095
deref_lookup(Imported, LookupOp),
1096
SelectorFun, Imported, LookupOp),
1097
ColumnConstants1 = lists:flatten(ColumnConstants0),
1100
{{GId,Col},Vals} <- ColumnConstants1 -- PatternConstants,
1103
ColumnConstants = lu_skip(ColumnConstants1, FilterData, PatternFrame,
1104
PatternVars, Dependencies, State,
1105
Imported, LookupOp),
1106
{ColumnConstants, ExtraConstants}.
1108
%%% ** Comparing Terms **
1109
%%% When comparing the key against a term where some integer (or float
1110
%%% comparing equal to an integer) occurs, one has to be careful if the
1111
%%% table matches keys. One way would be to look up the term both with
1112
%%% the integer and with the float comparing equal to the integer--then
1113
%%% all objects that could possibly be answers are filtered (with
1114
%%% reasonable assumptions). But if integers occur several times in the
1115
%%% term all combinations have to be looked up, and that could be just
1117
%%% If imported variables occur in the term one could assume at compile
1118
%%% time that they are not integers and check that assumption at
1119
%%% runtime. However, this would probably be bad design since some keys
1120
%%% can be looked up, but others cannot.
1121
%%% However, the current implementation is simple: do not bind a
1122
%%% variable to a term if imported variables or integers occur in the
1125
deref_lookup(Imported, '==') ->
1126
%% Comparing table. Every value can be looked up.
1127
fun(PV, F) -> deref_values(PV, F, Imported) end;
1128
deref_lookup(Imported, '=:=') ->
1129
%% Matching table. Ignore comparisons unless the value is free of
1130
%% integers. See also Comparing Terms.
1131
BFun = fun(DV, Op) ->
1132
Op =:= '=:=' orelse free_of_integers(DV, Imported)
1134
fun(PV, F) -> deref_values(PV, F, BFun, Imported) end.
1046
1136
%% Augment ColConstants with filters that do not need to be run
1047
1137
%% provided that constants are looked up.
1048
lu_skip(ColConstants, FilterData, BindFun, Selector, PatternFrame,
1049
PatternVars, Dependencies, State) ->
1138
%% Does not find all filters that can be removed.
1139
lu_skip(ColConstants, FilterData, PatternFrame, PatternVars,
1140
Dependencies, State, Imported, LookupOp) ->
1050
1141
%% If there is a test that does not compare or match, then the
1051
1142
%% filter cannot be skipped.
1052
FailSelector = fun(_Value) -> true end,
1143
FailSelector = fun(_Frame) -> fun(Value) -> {yes, Value} end end,
1053
1144
%% In runtime, constants are looked up and matched against a pattern
1054
1145
%% (the pattern acts like a filter), then the filters are run.
1055
1146
PatternFrames = frame2frames(PatternFrame),
1056
1147
PatternColumns =
1057
flatten([frames_to_columns(PatternFrames, PV, QId, FailSelector) ||
1058
{QId,PV} <- PatternVars]),
1148
lists:flatten(frames_to_columns(PatternFrames, PatternVars,
1149
deref_pattern(Imported), FailSelector,
1150
Imported, LookupOp)),
1059
1152
%% Note: ColFil can contain filters for columns that cannot be
1060
1153
%% looked up. Such (possibly bogus) elements are however not used.
1061
1154
%% Note: one filter at a time is tested; only the pattern is
1102
1206
{value, {Column,LUCs}} -> LUCs
1104
bindings_is_subset(Frame, F2)
1105
and (Constants -- LookedUpConstants =:= [])
1208
%% Don't try to handle filters that compare several
1209
%% values equal. See also frames_to_columns().
1210
length(VarValues) =< 1 andalso
1211
(Constants -- LookedUpConstants =:= []) andalso
1212
bindings_is_subset(Frame, F2, Imported)
1107
1214
ColFils = family_list(ColFil),
1108
%% The atom 'all' means that all filters are covered by the lookup.
1215
%% The skip tag 'all' means that all filters are covered by the lookup.
1109
1216
%% It does not imply that there is only one generator as is the case
1110
1217
%% for match specifications (see match_spec_quals above).
1111
[{Col,Constants,case keysearch(Col, 1, ColFils) of
1112
{value, {Col, FilL}} ->
1114
length(FilterData) =:= length(FilL) ->
1122
end} || {Col,Constants} <- ColConstants].
1218
[{Col, Constants, skip_tag(Col, ColFils, FilterData)} ||
1219
{Col,Constants} <- ColConstants].
1221
deref_skip(E, F, _LookupOp, Imported) ->
1222
deref(E, F, Imported).
1224
deref_lu_skip('==', Imported) ->
1225
%% Comparing table. Cannot skip filters that match integers.
1226
BFun = fun(DV, Op) ->
1227
Op =:= '==' orelse free_of_integers(DV, Imported)
1229
fun(PV, F) -> deref_values(PV, F, BFun, Imported) end;
1230
deref_lu_skip('=:=', Imported) ->
1231
%% Matching table. Skip filters regardless of operator.
1232
fun(PV, F) -> deref_values(PV, F, Imported) end.
1124
1234
equal_columns(Qualifiers, AllIVs, Dependencies, State) ->
1125
Cs = equal_columns2(Qualifiers, AllIVs, Dependencies, State),
1236
join_info(Qualifiers, AllIVs, Dependencies, State, _JoinOp = '=='),
1237
join_gens(Cs, Qualifiers, Skip).
1128
1239
eq_columns(Qualifiers, AllIVs, Dependencies, State) ->
1129
Cs = eq_columns2(Qualifiers, AllIVs, Dependencies, State),
1241
join_info(Qualifiers, AllIVs, Dependencies, State, _JoinOp = '=:='),
1242
join_gens(Cs, Qualifiers, Skip).
1132
%% Group columns of the same generator together.
1133
%% -> {TwoGen, ManyGens}
1244
%% -> {TwoGens, ManyGens}
1245
join_gens(Cs0, Qs, Skip) ->
1135
1246
Cs = [family_list(C) || C <- Cs0],
1136
{[C || C <- Cs, length(C) =:= 2],
1137
[C || C <- Cs, length(C) > 2]}.
1139
%% Tries to find columns (possibly in the same table) that are
1140
%% matched (=:=/2) or compared (==/2). Unification again.
1141
%% -> [[{QualifierNumber,ColumnNumber}]] % Eq.classes.
1143
equal_columns2(Qualifiers, AllIVs, Dependencies, State) ->
1144
BindFun = fun(Imp) -> fun(V, Op) -> is_no_const(V, Op, Imp) end end,
1145
join_info(Qualifiers, AllIVs, Dependencies, BindFun, State).
1147
%% Tries to find columns (possibly in the same table) that are matched
1149
%% -> [[{QualifierNumber,ColumnNumber}]] % Eq.classes.
1151
eq_columns2(Qualifiers, AllIVs, Dependencies, State) ->
1152
BindFun = fun(Imp) -> fun(V, Op) -> is_match_no_const(V, Op, Imp) end end,
1153
join_info(Qualifiers, AllIVs, Dependencies, BindFun, State).
1155
join_info(Qualifiers, AllIVs, Dependencies, BindFun0, State) ->
1247
{FD, _GeneratorData} = qual_data(Qs),
1248
{join_gens2(lists:filter(fun(C) -> length(C) =:= 2 end, Cs), FD, Skip),
1249
join_gens2(lists:filter(fun(C) -> length(C) > 2 end, Cs), FD, Skip)}.
1251
join_gens2(Cs0, FilterData, Skip) ->
1252
[{J, skip_tag(case lists:keysearch(J, 1, Skip) of
1253
{value, {J,FilL}} ->
1257
end, FilterData)} ||
1258
J <- lists:append([qlc:all_selections(C) || C <- Cs0])].
1260
skip_tag(FilList, FilterData) ->
1262
length(FilterData) =:= length(FilList) ->
1268
skip_tag(Col, ColFils, FilterData) ->
1269
case lists:keysearch(Col, 1, ColFils) of
1270
{value, {Col, FilL}} ->
1272
length(FilterData) =:= length(FilL) ->
1282
%% Tries to find columns (possibly in the same table) that are equal.
1283
%% If LookupOp is '=:=' then "equal" means that the columns are matched;
1284
%% if LookupOp is '==' then "equal" means that the columns are matched or
1286
%% -> [[{QualifierNumber,ColumnNumber}]] % Eq.classes.
1287
join_info(Qualifiers, AllIVs, Dependencies, State, JoinOp) ->
1156
1288
{FilterData, GeneratorData} = qual_data(Qualifiers),
1157
1289
{Filter, Anon1, Imported} =
1158
1290
filter_info(FilterData, AllIVs, Dependencies, State),
1159
BindFun = BindFun0(Imported),
1291
BindFun = fun(_Op, V) -> bind_no_const(V, Imported) end,
1160
1292
{PatternFrame, PatternVars} =
1161
1293
pattern_frame(GeneratorData, BindFun, Anon1, State),
1162
1294
PatternFrames = frame2frames(PatternFrame),
1163
SkipFun = fun(Fs) -> Fs end,
1164
Fs = filter(Filter, PatternFrames, BindFun, SkipFun, State),
1165
Selector = fun(Value) -> not is_const(Value, Imported) end,
1166
join_classes(fun(PV, QId) -> frames_to_columns(Fs, PV, QId, Selector)
1169
join_classes(FramesFun, PatternVars) ->
1170
Cols0 = [FramesFun(PV, QId) || {QId,PV} <- PatternVars],
1171
ColVar = sofs:relation(append(Cols0)),
1295
Fs = filter(Filter, PatternFrames, BindFun, State, Imported),
1296
SelectorFun = no_const_selector(Imported),
1297
Cols = frames_to_columns(Fs, PatternVars,
1298
fun(PV1, F) -> deref_join(PV1, F, JoinOp) end,
1299
SelectorFun, Imported, '=:='),
1300
JC = join_classes(Cols),
1301
Skip = join_skip(JC, FilterData, PatternFrame,
1302
PatternVars, Dependencies, State, Imported, JoinOp),
1305
deref_join(E, Frame, '==') ->
1306
deref_values(E, Frame, _Imp = []);
1307
deref_join(E, Frame, '=:=') ->
1308
%% Matching table. It is possible that some objects read from the
1309
%% other table (the one with the objects to look up) contain
1310
%% integers. By making all variables imported it is ensured that
1311
%% comparisons are kept. See also Comparing Terms.
1312
deref_values(E, Frame, fun(_DV, Op) -> Op =:= '=:=' end, all).
1314
join_classes(Cols0) ->
1315
ColVar = sofs:relation(lists:append(Cols0)),
1172
1316
Cols = sofs:partition(2, ColVar),
1173
1317
[[C || {C,_} <- Cs] || Cs <- sofs:to_external(Cols), length(Cs) > 1].
1319
join_skip(JoinClasses, FilterData, PatternFrame, PatternVars, Dependencies,
1320
State, Imported, JoinOp) ->
1321
PatternFrames = frame2frames(PatternFrame),
1322
ColFil = [{JoinClass,FId#qid.no} ||
1323
[{Q1,C1}, {Q2,C2}]=JoinClass <- JoinClasses,
1324
{GId1, PV1} <- PatternVars,
1326
{GId2, PV2} <- PatternVars,
1329
%% Select a filter that depends on the two generators:
1331
filter_list(FilterData, Dependencies, State),
1333
[lists:keysearch(FId, 1, Dependencies)],
1334
GIds =:= lists:sort([GId1,GId2]),
1337
%% Do what the join does:
1338
%% element(C1, G1) JoinOp element(C2, G2).
1339
%% As for lu_skip: sometimes it would be
1340
%% advantageously to assume some filter(s)
1341
%% occurring before the join filter had been run
1343
BindFun = fun(_Op, V) -> is_bindable(V) end,
1345
unify_column(PatternFrame, PV1, C1, BindFun, Imported),
1347
unify_column(JF1, PV2, C2, BindFun, Imported),
1348
JF = unify(JoinOp, V1, V2, JF2, BindFun, Imported),
1350
%% "Run" the filter:
1351
SFs = safe_filter(set_line(Fil, 0), PatternFrames,
1352
BindFun, State, Imported),
1353
JImp = qlc:vars([SFs, JF]), % kludge
1354
lists:all(fun(Frame) ->
1355
bindings_is_subset(Frame, JF, JImp)
1356
end, SFs) andalso SFs =/= []
1358
family_list(ColFil).
1175
1360
filter_info(FilterData, AllIVs, Dependencies, State) ->
1176
1361
FilterList = filter_list(FilterData, Dependencies, State),
1177
1362
Filter0 = set_line(filters_as_one(FilterList), 0),
1179
1364
{Filter, Anon1} = anon_var(Filter0, Anon0),
1180
Imported = ordsets:subtract(vars(Filter), % anonymous too
1365
Imported = ordsets:subtract(qlc:vars(Filter), % anonymous too
1366
ordsets:from_list(AllIVs)),
1182
1367
{Filter, Anon1, Imported}.
1184
1369
%% Selects the guard filters. Other filters than guard filters are
1236
1421
end, {Frame0, Anon1, []}, GeneratorData),
1237
1422
{PatternFrame, PatternVars}.
1239
is_match_no_const(Value, Op, Imported) ->
1240
(Op =/= '==') andalso is_no_const(Value, Op, Imported).
1242
is_no_const(Value, Op, Imported) ->
1243
is_bindable(Value, Op, Imported) andalso not is_const(Value, Imported).
1424
const_selector(Imported) ->
1425
selector(Imported, fun is_const/2).
1427
no_const_selector(Imported) ->
1428
selector(Imported, fun(V, I) -> not is_const(V, I) end).
1430
selector(Imported, TestFun) ->
1433
case TestFun(Value, Imported) of
1442
bind_no_const(Value, Imported) ->
1443
case is_const(Value, Imported) of
1245
1450
%% Tuple tails are variables, never constants.
1246
1451
is_const(Value, Imported) ->
1247
1452
%% is_bindable() has checked that E is normalisable.
1248
[] =:= ordsets:to_list(ordsets:subtract(vars(Value), Imported)).
1250
%% If there is an integer (or float comparing equal to an integer) in
1251
%% the value one has to be careful. One way would be to look up the
1252
%% value both with the integer and with the float comparing equal to
1253
%% the integer - then all objects that could possibly be answers are
1254
%% filtered (with reasonable assumptions). But if integers occur
1255
%% several times in the value all combinations have to be looked up,
1256
%% and that could be just too many.
1258
%% If there are imported variables in the value one could assume at
1259
%% compile time that they are not integers and check that assumption
1260
%% at runtime. However, this implementation is much simpler: do not
1261
%% bind the variable to the value if imported variables or integers
1262
%% occur in the value. This will probably do.
1264
is_bindable(Value, Op, Imp) ->
1453
[] =:= ordsets:to_list(ordsets:subtract(qlc:vars(Value), Imported)).
1455
is_bindable(Value) ->
1265
1456
case normalise(Value) of
1266
{ok, NValue} when Op =:= '==' ->
1267
case {ordsets:to_list(ordsets:intersection(vars(Value), Imp)),
1268
has_integer(NValue)} of
1274
{ok, _} when Op =:= '=:=' ->
1388
1571
filter1({call,L,{remote,L1,{atom,_,erlang}=M,{atom,L2,is_record}},[T,R,_Sz]},
1390
1573
filter1({call,L,{remote,L1,M,{atom,L2,is_record}},[T,R]}, Fs, FS);
1391
filter1(_E, Fs, FS) ->
1392
(FS#fstate.skip_fun)(Fs).
1574
filter1(_E, Fs, _FS) ->
1394
1577
%% filter() tries to extract as much information about constant
1395
1578
%% columns as possible. It ignores those parts of the filter that are
1396
1579
%% uninteresting. safe_filter() on the other hand ensures that the
1397
%% bindings returned capture _all_ aspects of the filter.
1398
safe_filter(_E, []=Frames0, _BF, _State) ->
1580
%% bindings returned capture _all_ aspects of the filter (wrt BF).
1581
safe_filter(_E, []=Frames0, _BF, _State, _Imported) ->
1400
safe_filter(E0, Frames0, BF, State) ->
1583
safe_filter(E0, Frames0, BF, State, Imported) ->
1401
1584
E = pre_expand(E0),
1402
FailFun = fun(_Fs) -> [] end,
1403
FState = #fstate{state = State, bind_fun = BF, skip_fun = FailFun},
1585
FState = #fstate{state = State, bind_fun = BF, imported = Imported},
1404
1586
safe_filter1(E, Frames0, FState).
1406
1588
safe_filter1({op, _, Op, L0, R0}, Fs, FS) when Op =:= '=:='; Op =:= '==' ->
1407
#fstate{state = S, bind_fun = BF} = FS,
1409
{L, F1} = prep_expr(L0, F0, S, BF),
1410
{R, F2} = prep_expr(R0, F1, S, BF),
1411
case safe_unify(Op, L, R, F2, BF) of
1589
#fstate{state = S, bind_fun = BF, imported = Imported} = FS,
1590
lists:flatmap(fun(F0) ->
1591
{L, F1} = prep_expr(L0, F0, S, BF, Imported),
1592
{R, F2} = prep_expr(R0, F1, S, BF, Imported),
1593
case safe_unify(Op, L, R, F2, BF, Imported) of
1416
1598
safe_filter1({op, _, Op, L, R}, Fs, FS) when Op =:= 'and'; Op =:= 'andalso' ->
1417
1599
safe_filter1(R, safe_filter1(L, Fs, FS), FS);
1418
1600
safe_filter1({op, _, Op, L, R}, Fs, FS) when Op =:= 'or'; Op =:= 'orelse' ->
1419
1601
safe_filter1(L, Fs, FS) ++ safe_filter1(R, Fs, FS);
1420
safe_filter1({atom,_,Atom}, _Fs, _FS) when Atom =/= true ->
1422
safe_filter1(_E, Fs, FS) ->
1423
(FS#fstate.skip_fun)(Fs).
1602
safe_filter1({atom,_,true}, Fs, _FS) ->
1604
safe_filter1(_E, _Fs, _FS) ->
1425
1607
%% Substitutions:
1426
1608
%% M:F() for {M,F}(); erlang:F() for F(); is_record() for record().
1437
1619
pre_expand(T) ->
1440
column_i(Frame, PatternVar, I) ->
1441
{cons_tuple, Cs} = deref({var, 0, PatternVar}, Frame),
1442
column_i_2(Cs, 1, I).
1444
column_i_2({cons,_,V,_}, I, I) ->
1446
column_i_2({cons,_,_,E}, I, N) ->
1447
column_i_2(E, I+1, N).
1449
pattern_size(Fs, PatternVar) ->
1450
Szs = [case deref({var, 0, PatternVar}, F) of
1451
{cons_tuple, Cs} -> pattern_sz(Cs, 0);
1454
case lists:usort(Szs) of
1455
[Sz] when Sz >= 0 -> Sz;
1459
pattern_sz({cons,_,_C,E}, Col) ->
1460
pattern_sz(E, Col+1);
1461
pattern_sz({nil,_}, Sz) ->
1463
pattern_sz(_, _Sz) ->
1466
%% -> [{{QualifierNumber,ColumnNumber}, [Value]}]
1467
frames_to_columns(Fs, PatternVar, PatternId, Selector) ->
1468
F = fun({cons_tuple, Cs}) ->
1469
sel_columns(Cs, 1, PatternId, Selector);
1473
all_frames(Fs, PatternVar, F).
1475
sel_columns({cons,_,C,E}, Col, PId, Selector) ->
1478
V = {{PId#qid.no,Col},cons2tuple(C)},
1479
[V | sel_columns(E, Col+1, PId, Selector)];
1481
sel_columns(E, Col+1, PId, Selector)
1483
sel_columns(_, _Col, _PId, _Selector) ->
1486
all_frames([], _PatternVar, _DerefFun) ->
1622
%% -> [ [{{QualifierNumber,ColumnNumber}, [Value]}] ]
1623
frames_to_columns([], _PatternVars, _DerefFun, _SelectorFun, _Imp, _CompOp) ->
1488
all_frames(Fs, PatternVar, DerefFun) ->
1490
Deref = deref({var, 0, PatternVar}, F),
1491
RL = DerefFun(Deref),
1492
sofs:relation(RL) % possibly empty
1625
frames_to_columns(Fs, PatternVars, DerefFun, SelectorFun, Imp, CompOp) ->
1626
%% It is important that *the same* variables are introduced for
1627
%% columns in every frame. (When trying to find constant columns
1628
%% it doesn't matter, but when trying to find joined columns, the
1629
%% same variables have to be the representatives in every frame.)
1632
PatVar = {var,0,PV},
1633
PatternSizes = [pattern_size([F], PatVar, false) ||
1635
MaxPZ = lists:max([0 | PatternSizes -- [undefined]]),
1636
Vars = pat_vars(MaxPZ),
1637
{PatternId#qid.no, PatVar, PatternSizes, Vars}
1638
end || {PatternId, PV} <- PatternVars],
1639
BF = fun(_Op, Value) -> is_bindable(Value) end,
1640
Fun = fun({_PatN, PatVar, PatSizes, Vars}, Frames) ->
1641
[unify('=:=', pat_tuple(Sz, Vars), PatVar, Frame, BF, Imp) ||
1642
{Sz, Frame} <- lists:zip(PatSizes, Frames)]
1644
NFs = lists:foldl(Fun, Fs, SizesVarsL),
1645
[frames2cols(NFs, PatN, PatSizes, Vars, DerefFun, SelectorFun, CompOp) ||
1646
{PatN, _PatVar, PatSizes, Vars} <- SizesVarsL].
1648
frames2cols(Fs, PatN, PatSizes, Vars, DerefFun, SelectorFun, CompOp) ->
1650
RL = [{{PatN,Col},cons2tuple(element(2, Const))} ||
1651
{V, Col} <- lists:zip(sublist(Vars, PatSz),
1653
%% Do not handle the case where several
1654
%% values compare equal, e.g. "X =:= 1
1655
%% andalso X == 1.0". Looking up both
1656
%% values or one of them won't always do
1657
%% because it is more or less undefined
1658
%% whether the table returns the given key
1659
%% or the one stored in the table. Or
1660
%% rather, it would be strange if the table
1661
%% did not return the stored key upon
1662
%% request, but the 'lookup_fun' function
1663
%% may have to add the given key (see also
1664
%% gb_table in qlc(3)). (Not a very strong
1665
%% argument. "X =:= 1" could (should?) be
1666
%% seen as a bug.) Note: matching tables
1667
%% cannot skip the filter, but looking up
1668
%% one of the values should be OK.
1669
tl(Consts = DerefFun(V, F)) =:= [],
1670
(Const = (SelectorFun(F))(hd(Consts))) =/= no],
1671
sofs:relation(RL) % possibly empty
1672
end || {F,PatSz} <- lists:zip(Fs, PatSizes)],
1494
1673
Ss = sofs:from_sets(Rs),
1495
1674
%% D: columns occurring in every frame (path).
1496
1675
D = sofs:intersection(sofs:projection(fun(S) -> sofs:projection(1, S) end,
1498
1677
Cs = sofs:restriction(sofs:relation_to_family(sofs:union(Ss)), D),
1499
sofs:to_external(Cs).
1501
prep_expr(E, F, S, BF) ->
1502
element_calls(tuple2cons(expand_expr_records(E, S)), F, BF).
1678
[C || {_,Vs}=C <- sofs:to_external(Cs), not col_ignore(Vs, CompOp)].
1681
[unique_var() || _ <- seq(1, N)].
1683
pat_tuple(Sz, Vars) when is_integer(Sz), Sz > 0 ->
1684
TupleTail = unique_var(),
1685
{cons_tuple, list2cons(sublist(Vars, Sz) ++ TupleTail)};
1686
pat_tuple(_, _Vars) ->
1689
%% Do not handle tests as "X =:= 1.0 orelse X == 1" either.
1690
%% Similar problems as described above.
1691
col_ignore(_Vs, '=:=') ->
1693
col_ignore(Vs, '==') ->
1694
length(Vs) =/= length(lists:usort([element(2, normalise(V)) || V <- Vs])).
1696
pattern_sizes(PatternVars, Fs) ->
1697
[{QId#qid.no, Size} ||
1698
{QId,PV} <- PatternVars,
1699
undefined =/= (Size = pattern_size(Fs, {var,0,PV}, true))].
1701
pattern_size(Fs, PatternVar, Exact) ->
1702
Fun = fun(F) -> (deref_pattern(_Imported = []))(PatternVar, F) end,
1703
Derefs = lists:flatmap(Fun, Fs),
1704
Szs = [pattern_sz(Cs, 0, Exact) || {cons_tuple, Cs} <- Derefs],
1705
case lists:usort(Szs) of
1706
[Sz] when is_integer(Sz), Sz >= 0 -> Sz;
1707
[] when not Exact -> 0;
1711
pattern_sz({cons,_,_C,E}, Col, Exact) ->
1712
pattern_sz(E, Col+1, Exact);
1713
pattern_sz({nil,_}, Sz, _Exact) ->
1715
pattern_sz(_, _Sz, true) ->
1717
pattern_sz(_, Sz, false) ->
1720
deref_pattern(Imported) ->
1721
fun(PV, F) -> deref_values(PV, F, Imported) end.
1723
prep_expr(E, F, S, BF, Imported) ->
1724
element_calls(tuple2cons(expand_expr_records(E, S)), F, BF, Imported).
1726
unify_column(Frame, Var, Col, BindFun, Imported) ->
1727
Call = {call,0,{atom,0,element},[{integer,0,Col}, {var,0,Var}]},
1728
element_calls(Call, Frame, BindFun, Imported).
1504
1730
%% cons_tuple is used for representing {V1, ..., Vi | TupleTail}.
1507
1733
%% {_, a | _}. The tail may be unified later, when more information
1508
1734
%% about the size of the tuple is known.
1509
1735
element_calls({call,_,{remote,_,{atom,_,erlang},{atom,_,element}},
1510
[{integer,_,I},Term0]}, F0, BF) when I > 0 ->
1511
VarI = unique_var(),
1736
[{integer,_,I},Term0]}, F0, BF, Imported) when I > 0 ->
1512
1737
TupleTail = unique_var(),
1513
Tuple = element_tuple(I, [VarI | TupleTail]),
1514
{Term, F} = element_calls(Term0, F0, BF),
1515
{VarI, unify('=:=', Tuple, Term, F, BF)};
1516
element_calls({call,L1,{atom,_,element}=E,As}, F0, BF) ->
1738
VarsL = [unique_var() || _ <- lists:seq(1, I)],
1739
Vars = VarsL ++ TupleTail,
1740
Tuple = {cons_tuple, list2cons(Vars)},
1741
VarI = lists:nth(I, VarsL),
1742
{Term, F} = element_calls(Term0, F0, BF, Imported),
1743
{VarI, unify('=:=', Tuple, Term, F, BF, Imported)};
1744
element_calls({call,L1,{atom,_,element}=E,As}, F0, BF, Imported) ->
1517
1745
%% erl_expand_records should add "erlang:"...
1518
element_calls({call,L1,{remote,L1,{atom,L1,erlang},E}, As}, F0, BF);
1519
element_calls(T, F0, BF) when is_tuple(T) ->
1520
{L, F} = element_calls(tuple_to_list(T), F0, BF),
1746
element_calls({call,L1,{remote,L1,{atom,L1,erlang},E}, As}, F0, BF,
1748
element_calls(T, F0, BF, Imported) when is_tuple(T) ->
1749
{L, F} = element_calls(tuple_to_list(T), F0, BF, Imported),
1521
1750
{list_to_tuple(L), F};
1522
element_calls([E0 | Es0], F0, BF) ->
1523
{E, F1} = element_calls(E0, F0, BF),
1524
{Es, F} = element_calls(Es0, F1, BF),
1751
element_calls([E0 | Es0], F0, BF, Imported) ->
1752
{E, F1} = element_calls(E0, F0, BF, Imported),
1753
{Es, F} = element_calls(Es0, F1, BF, Imported),
1526
element_calls(E, F, _BF) ->
1755
element_calls(E, F, _BF, _Imported) ->
1529
element_tuple(1, Es) ->
1530
{cons_tuple, list2cons(Es)};
1531
element_tuple(I, Es) ->
1532
element_tuple(I-1, [unique_var() | Es]).
1534
1758
unique_var() ->
1535
1759
{var, 0, make_ref()}.
1564
unify(Op, E1, E2, F, BF) ->
1565
unify(Op, E1, E2, F, BF, false).
1567
safe_unify(Op, E1, E2, F, BF) ->
1568
unify(Op, E1, E2, F, BF, true).
1570
unify(_Op, _E1, _E2, failed, _BF, _Safe) -> % contradiction
1788
unify(Op, E1, E2, F, BF, Imported) ->
1789
unify(Op, E1, E2, F, BF, Imported, false).
1791
safe_unify(Op, E1, E2, F, BF, Imported) ->
1792
unify(Op, E1, E2, F, BF, Imported, true).
1794
unify(_Op, _E1, _E2, failed, _BF, _Imported, _Safe) -> % contradiction
1572
unify(_Op, E, E, F, _BF, _Safe) ->
1796
unify(_Op, E, E, F, _BF, _Imported, _Safe) ->
1574
unify(Op, {var, _, _}=Var, E2, F, BF, Safe) ->
1575
extend_frame(Op, Var, E2, F, BF, Safe);
1576
unify(Op, E1, {var, _, _}=Var, F, BF, Safe) ->
1577
extend_frame(Op, Var, E1, F, BF, Safe);
1578
unify(Op, {cons_tuple, Es1}, {cons_tuple, Es2}, F, BF, Safe) ->
1579
unify(Op, Es1, Es2, F, BF, Safe);
1580
unify(Op, {cons, _, L1, R1}, {cons, _, L2, R2}, F, BF, Safe) ->
1581
unify(Op, R1, R2, unify(Op, L1, L2, F, BF, Safe), BF, Safe);
1582
unify(Op, E1, E2, F, _BF, Safe) ->
1583
%% This clause could just return F.
1798
unify(Op, {var, _, _}=Var, E2, F, BF, Imported, Safe) ->
1799
extend_frame(Op, Var, E2, F, BF, Imported, Safe);
1800
unify(Op, E1, {var, _, _}=Var, F, BF, Imported, Safe) ->
1801
extend_frame(Op, Var, E1, F, BF, Imported, Safe);
1802
unify(Op, {cons_tuple, Es1}, {cons_tuple, Es2}, F, BF, Imported, Safe) ->
1803
unify(Op, Es1, Es2, F, BF, Imported, Safe);
1804
unify(Op, {cons, _, L1, R1}, {cons, _, L2, R2}, F, BF, Imported, Safe) ->
1805
E = unify(Op, L1, L2, F, BF, Imported, Safe),
1806
unify(Op, R1, R2, E, BF, Imported, Safe);
1807
unify(Op, E1, E2, F, _BF, _Imported, Safe) ->
1585
1809
{ok, C1} = normalise(E1),
1586
1810
{ok, C2} = normalise(E2),
1595
1819
catch error:_ when Safe -> failed;
1596
1820
error:_ when not Safe -> F % ignored
1598
%% Binaries are not handled at all.
1600
-record(bind, {var, value}).
1602
extend_frame(Op, Var, Value, F, BF, Safe) ->
1603
case binding(Var, F) of
1604
#bind{var = Var, value = VarValue} ->
1605
unify(Op, VarValue, Value, F, BF, Safe);
1822
%% Binaries are not handled at all (by unify).
1824
%% Note that a variable can be bound to several values, for instance:
1825
%% X =:= 3, X == 3.0. As a consequence, deref() returns a list of
1828
%% Binding a variable to several values makes the unification and
1829
%% dereferencing more complicated. An alternative would be not to try
1830
%% to find lookup values for such QLCs at all. That might have been a
1831
%% better design decision.
1833
-record(bind, {var, value, op}).
1835
extend_frame(Op, Var, Value, F, BF, Imported, Safe) ->
1836
case var_values(Var, F) of
1609
case binding(Value, F) of
1610
#bind{var = Value, value = ValueValue} ->
1611
unify(Op, Var, ValueValue, F, BF, Safe);
1613
add_binding(Op, Var, Value, F, BF)
1840
case var_values(Value, F) of
1842
add_binding(Op, Value, Var, F, BF, Imported, Safe);
1844
maybe_add_binding(ValsOps, Op, Value, Var, F,
1616
add_binding(Op, Var, Value, F, BF)
1848
add_binding(Op, Var, Value, F, BF, Imported, Safe)
1851
maybe_add_binding(ValsOps, Op, Var, Value, F, BF, Imported, Safe)
1854
maybe_add_binding(ValsOps, Op, Var, Value, F0, BF, Imported, Safe) ->
1855
case unify_var_bindings(ValsOps, Op, Value, F0, BF, Imported, Safe) of
1859
case already_bound(Op, Var, Value, F) of
1863
add_binding(Op, Var, Value, F, BF, Imported, Safe)
1620
add_binding(Op, Var, Value, F, BF) ->
1621
case BF(Value, Op) of
1623
add_binding(Var, Value, F);
1867
already_bound(Op, Var, Value, F) ->
1868
%% Note: all variables are treated as imported. The dereferenced
1869
%% values must not depend on Imported.
1870
BFun = fun(_DV, BOp) -> Op =:= BOp end,
1871
DerefValue = deref_value(Value, Op, F, BFun, all),
1872
DerefVar = deref_var(Var, F, BFun, all),
1873
DerefValue -- DerefVar =:= [].
1875
unify_var_bindings([], _Op, _Value, F, _BF, _Imported, _Safe) ->
1877
unify_var_bindings([{VarValue, Op2} | Bindings],
1878
Op1, Value, F0, BF, Imported, Safe) ->
1879
Op = deref_op(Op1, Op2),
1880
case unify(Op, VarValue, Value, F0, BF, Imported, Safe) of
1884
unify_var_bindings(Bindings, Op1, Value, F, BF, Imported, Safe)
1887
deref_op('=:=', '=:=') ->
1892
%%% Note: usort works; {integer,L,3} does not match {float,L,3.0}.
1894
var_values(Var, Frame) ->
1896
#bind{value = Value, op = Op} <- var_bindings(Var, Frame)].
1898
deref_var(Var, Frame, Imported) ->
1899
deref_var(Var, Frame, fun(_DV, _Op) -> true end, Imported).
1901
deref_var(Var, Frame, BFun, Imported) ->
1902
lists:usort([ValOp ||
1903
#bind{value = Value, op = Op} <- var_bindings(Var, Frame),
1904
ValOp <- deref_value(Value, Op, Frame, BFun, Imported)]).
1906
deref_value(Value, Op, Frame, BFun, Imported) ->
1907
lists:usort([{Val,value_op(ValOp, Op, Imported)} ||
1908
{Val,_Op}=ValOp <- deref(Value, Frame, BFun, Imported)]).
1910
add_binding(Op, Var0, Value0, F, BF, Imported, Safe) ->
1911
{Var, Value} = maybe_swap_var_value(Var0, Value0, F, Imported),
1912
case BF(Op, Value) of
1914
add_binding2(Var, Value, Op, F);
1917
false when not Safe ->
1628
add_binding(Var, Value, F) ->
1629
case {occurs(Var, Value, F), Value} of
1921
add_binding2(Var, Value, Op, F) ->
1922
case occurs(Var, Value, F) of
1632
{false, {var, _, Ref}} when is_reference(Ref) ->
1633
%% Push imported variables to the end of the binding chain
1634
%% in order to make is_const/1 work.
1635
[#bind{var = Value, value = Var} | F];
1637
[#bind{var = Var, value = Value} | F]
1926
[#bind{var = Var, value = Value, op = Op} | F]
1929
%% Ensure that imported variables are visible in the dereferenced
1930
%% value by pushing them to the end of the binding chain. Be careful
1931
%% not to introduce loops.
1932
maybe_swap_var_value(Var, Value, Frame, Imported) ->
1933
case do_swap_var_value(Var, Value, Frame, Imported) of
1940
do_swap_var_value({var, _, V1}=Var1, {var, _, V2}=Var2, F, Imported) ->
1941
case swap_vv(Var1, Var2, F) of
1943
case swap_vv(Var2, Var1, F) of
1945
ordsets:is_element(V1, Imported) andalso
1946
not ordsets:is_element(V2, Imported);
1953
do_swap_var_value(_, _, _F, _Imp) ->
1956
swap_vv(V1, V2, F) ->
1957
[V || #bind{value = V} <- var_bindings(V1, F), V =:= V2].
1640
1959
normalise(E) ->
1641
1960
%% Tuple tails are OK.
1649
1968
occurs(V, V, _F) ->
1651
1970
occurs(V, {var, _, _} = Var, F) ->
1652
case binding(Var, F) of
1653
#bind{value = Value} ->
1654
occurs(V, Value, F);
1971
lists:any(fun(B) -> occurs(V, B#bind.value, F) end, var_bindings(Var, F));
1658
1972
occurs(V, T, F) when is_tuple(T) ->
1659
1973
lists:any(fun(E) -> occurs(V, E, F) end, tuple_to_list(T));
1660
1974
occurs(V, [E | Es], F) ->
1661
occurs(V, E, F) or occurs(V, Es, F);
1975
occurs(V, E, F) orelse occurs(V, Es, F);
1662
1976
occurs(_V, _E, _F) ->
1665
has_integer(I) when is_integer(I) ->
1667
has_integer(F) when is_float(F) ->
1669
has_integer(T) when is_tuple(T) ->
1670
has_integer(tuple_to_list(T));
1671
has_integer([E | Es]) ->
1672
has_integer(E) or has_integer(Es);
1678
case binding(V, F) of
1679
#bind{value = Val} ->
1686
binding(V, [#bind{var = V}=B | _]) ->
1688
binding(V, [_ | F]) ->
1979
deref_values(E, Frame, Imported) ->
1980
deref_values(E, Frame, fun(_DV, _Op) -> true end, Imported).
1982
deref_values(E, Frame, BFun, Imported) ->
1984
{V, Op} <- deref(E, Frame, BFun, Imported),
1988
BFun = fun(_DV, _Op) -> true end,
1989
deref(E, F, BFun, Imp).
1991
deref({var, _, _}=V, F, BFun, Imp) ->
1992
DBs = lists:flatmap(fun(B) -> deref_binding(B, F, BFun, Imp)
1993
end, var_bindings(V, F)),
2000
deref(T, F, BFun, Imp) when is_tuple(T) ->
2001
[{list_to_tuple(DL), Op} ||
2002
{DL, Op} <- deref(tuple_to_list(T), F, BFun, Imp)];
2003
deref(Es, F, BFun, Imp) when is_list(Es) ->
2004
L = [deref(C, F, BFun, Imp) || C <- Es],
2005
lists:usort([deref_list(S) || S <- all_comb(L)]);
2006
deref(E, _F, _BFun, _Imp) ->
2009
var_bindings(Var, F) ->
2010
[B || #bind{var = V}=B <- F, V =:= Var].
2012
deref_binding(Bind, Frame, BFun, Imp) ->
2013
#bind{value = Value, op = Op0} = Bind,
2015
{Val, _Op}=ValOp <- deref(Value, Frame, BFun, Imp),
2016
BFun(Val, Op = value_op(ValOp, Op0, Imp))].
2019
Op = case lists:usort([Op || {_Val, Op} <- L]) of
2025
{[V || {V, _Op} <- L], Op}.
2027
value_op({_V, '=='}, _BindOp, _Imp) ->
2029
value_op({_V, '=:='}, _BindOp='=:=', _Imp) ->
2031
value_op({V, '=:='}, _BindOp='==', Imp) ->
2032
case free_of_integers(V, Imp) of
2041
all_comb([Cs | ICs]) ->
2042
[[C | L] || C <- Cs, L <- all_comb(ICs)].
2044
%% "Free of integers" here means that there are not imported variables
2045
%% in V (which could take on integer values), but there may be other
2047
free_of_integers(V, Imported) ->
2048
not has_integer(V) andalso not has_imported_vars(V, Imported).
2050
%% Assumes that imported variables are representatives, if Value is a
2051
%% dereferenced value.
2052
has_imported_vars(Value, all) ->
2053
qlc:vars(Value) =/= [];
2054
has_imported_vars(Value, Imported) ->
2055
[Var || Var <- qlc:vars(Value), lists:member(Var, Imported)] =/= [].
2057
has_integer(Abstr) ->
2060
catch throw:true -> true
2063
has_int({integer,_,I}) when float(I) == I ->
2065
has_int({float,_,F}) when round(F) == F ->
2067
has_int(T) when is_tuple(T) ->
2068
has_int(tuple_to_list(T));
2069
has_int([E | Es]) ->
1693
2075
tuple2cons({tuple, _, Es}) ->
added
removed
lib/stdlib/src/qlc_pt.erl
