FORM 4.3
smart.c
Go to the documentation of this file.
1
12/* #[ License : */
13/*
14 * Copyright (C) 1984-2022 J.A.M. Vermaseren
15 * When using this file you are requested to refer to the publication
16 * J.A.M.Vermaseren "New features of FORM" math-ph/0010025
17 * This is considered a matter of courtesy as the development was paid
18 * for by FOM the Dutch physics granting agency and we would like to
19 * be able to track its scientific use to convince FOM of its value
20 * for the community.
21 *
22 * This file is part of FORM.
23 *
24 * FORM is free software: you can redistribute it and/or modify it under the
25 * terms of the GNU General Public License as published by the Free Software
26 * Foundation, either version 3 of the License, or (at your option) any later
27 * version.
28 *
29 * FORM is distributed in the hope that it will be useful, but WITHOUT ANY
30 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
31 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
32 * details.
33 *
34 * You should have received a copy of the GNU General Public License along
35 * with FORM. If not, see <http://www.gnu.org/licenses/>.
36 */
37/* #] License : */
38/*
39 #[ Includes : function.c
40*/
41
42#include "form3.h"
43
44/*
45 #] Includes :
46 #[ StudyPattern :
47
48 Argument is a complete lhs of an id-statement
49 Its last word is a zero (new convention(18-may-1997)) to indicate
50 that no extra information is following. We can add there information
51 about the pattern that will help during the actual pattern matching.
52 Currently the WorkPointer points to just after this lhs.
53
54 Task of this routine: To study the functions, their symmetry properties
55 and their wildcards to determine in which order the functions can
56 be matched best. If the order should be different we can change it here.
57
58 Problem encountered 22-dec-2008 (JV): we don't take noncommuting
59 functions into account.
60*/
61
62int StudyPattern(WORD *lhs)
63{
64 GETIDENTITY
65 WORD *fullproto, *pat, *p, *p1, *p2, *pstop, *info, f, nn;
66 int numfun = 0, numsym = 0, allwilds = 0, i, j, k, nc;
67 FUN_INFO *finf, *fmin, *f1, *f2, funscratch;
68
69 fullproto = lhs + IDHEAD;
70/* if ( *lhs == TYPEIF ) fullproto--; */
71 pat = fullproto + fullproto[1];
72 info = pat + *pat;
73
74 p = pat + 1;
75 while ( p < info ) {
76 if ( *p >= FUNCTION ) {
77 numfun++;
78 nn = *p - FUNCTION;
79 if ( nn >= WILDOFFSET ) nn -= WILDOFFSET;
80/*
81 We check here for cases that are not allowed like ?a inside
82 symmetric functions or tensors.
83*/
84 if ( ( functions[nn].symmetric == SYMMETRIC ) ||
85 ( functions[nn].symmetric == ANTISYMMETRIC ) ) {
86 p2 = p+p[1]; p1 = p+FUNHEAD;
87 if ( functions[nn].spec ) {
88 while ( p1 < p2 ) {
89 if ( *p1 == FUNNYWILD ) {
90 MesPrint("&Argument field wildcards are not allowed inside (anti)symmetric functions or tensors");
91 return(1);
92 }
93 p1++;
94 }
95 }
96 else {
97 while ( p1 < p2 ) {
98 if ( *p1 == -ARGWILD ) {
99 MesPrint("&Argument field wildcards are not allowed inside (anti)symmetric functions or tensors");
100 return(1);
101 }
102 NEXTARG(p1);
103 }
104 }
105 }
106 }
107 p += p[1];
108 }
109 if ( numfun == 0 ) return(0);
110 if ( ( lhs[2] & SUBMASK ) == SUBALL ) {
111 p = pat + 1;
112 while ( p < info ) {
113 if ( *p == SYMBOL || *p == VECTOR || *p == DOTPRODUCT || *p == INDEX ) {
114 MesPrint("&id,all can have only functions and/or tensors in the lhs.");
115 return(1);
116 }
117 p += p[1];
118 }
119 }
120/*
121 We need now some room for the information about the functions
122*/
123 if ( numfun > AN.numfuninfo ) {
124 if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
125 AN.numfuninfo = numfun + 10;
126 AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
127 }
128/*
129 Now collect the information. First the locations.
130*/
131 p = pat + 1; i = 0;
132 while ( p < info ) {
133 if ( *p >= FUNCTION ) AN.FunInfo[i++].location = p;
134 p += p[1];
135 }
136 for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
137 p = finf->location;
138 pstop = p + p[1];
139 f = *p;
140 if ( f > FUNCTION+WILDOFFSET ) f -= WILDOFFSET;
141 finf->numargs = finf->numfunnies = finf->numwildcards = 0;
142 finf->symmet = functions[f-FUNCTION].symmetric;
143 finf->tensor = functions[f-FUNCTION].spec;
144 finf->commute = functions[f-FUNCTION].commute;
145 if ( finf->tensor >= TENSORFUNCTION ) {
146 p += FUNHEAD;
147 while ( p < pstop ) {
148 if ( *p == FUNNYWILD ) {
149 finf->numfunnies++; p+= 2; continue;
150 }
151 else if ( *p < 0 ) {
152 if ( *p >= AM.OffsetVector + WILDOFFSET && *p < MINSPEC ) {
153 finf->numwildcards++;
154 }
155 }
156 else {
157 if ( *p >= AM.OffsetIndex + WILDOFFSET &&
158 *p <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
159 }
160 finf->numargs++;
161 p++;
162 }
163 }
164 else {
165 p += FUNHEAD;
166 while ( p < pstop ) {
167 if ( *p > 0 ) { finf->numargs++; p += *p; continue; }
168 if ( *p <= -FUNCTION ) {
169 if ( *p <= -FUNCTION - WILDOFFSET ) finf->numwildcards++;
170 p++;
171 }
172 else if ( *p == -SYMBOL ) {
173 if ( p[1] >= 2*MAXPOWER ) finf->numwildcards++;
174 p += 2;
175 }
176 else if ( *p == -INDEX ) {
177 if ( p[1] >= AM.OffsetIndex + WILDOFFSET &&
178 p[1] <= AM.OffsetIndex + 2*WILDOFFSET ) finf->numwildcards++;
179 p += 2;
180 }
181 else if ( *p == -VECTOR || *p == -MINVECTOR ) {
182 if ( p[1] >= AM.OffsetVector + WILDOFFSET && p[1] < MINSPEC ) {
183 finf->numwildcards++;
184 }
185 p += 2;
186 }
187 else if ( *p == -ARGWILD ) {
188 finf->numfunnies++;
189 p += 2;
190 }
191 else { p += 2; }
192 finf->numargs++;
193 }
194 }
195 if ( finf->symmet ) {
196 numsym++;
197 allwilds += finf->numwildcards + finf->numfunnies;
198 }
199 }
200 if ( numsym == 0 ) return(0);
201 if ( allwilds == 0 ) return(0);
202/*
203 We have the information in the array AN.FunInfo.
204 We sort things and then write the sorted pattern.
205 Of course we may not play with the order of the noncommuting functions.
206 Of course we have to become even smarter in the future and look during
207 the sorting which wildcards are asigned when.
208 But for now this should do.
209*/
210 for ( nc = numfun-1; nc >= 0; nc-- ) { if ( AN.FunInfo[nc].commute ) break; }
211
212 finf = AN.FunInfo;
213 for ( i = nc+2; i < numfun; i++ ) {
214 fmin = finf; finf++;
215 if ( ( finf->symmet < fmin->symmet ) || (
216 ( finf->symmet == fmin->symmet ) &&
217 ( ( finf->numwildcards+finf->numfunnies < fmin->numwildcards+fmin->numfunnies )
218 || ( ( finf->numwildcards+finf->numfunnies == fmin->numwildcards+fmin->numfunnies )
219 && ( finf->numwildcards < fmin->numfunnies ) ) ) ) ) {
220 funscratch = AN.FunInfo[i];
221 AN.FunInfo[i] = AN.FunInfo[i-1];
222 AN.FunInfo[i-1] = funscratch;
223 for ( j = i-1; j > nc && j > 0; j-- ) {
224 f1 = AN.FunInfo+j;
225 f2 = f1-1;
226 if ( ( f1->symmet < f2->symmet ) || (
227 ( f1->symmet == f2->symmet ) &&
228 ( ( f1->numwildcards+f1->numfunnies < f2->numwildcards+f2->numfunnies )
229 || ( ( f1->numwildcards+f1->numfunnies == f2->numwildcards+f2->numfunnies )
230 && ( f1->numwildcards < f2->numfunnies ) ) ) ) ) {
231 funscratch = AN.FunInfo[j];
232 AN.FunInfo[j] = AN.FunInfo[j-1];
233 AN.FunInfo[j-1] = funscratch;
234 }
235 else break;
236 }
237 }
238 }
239/*
240 Now we rewrite the pattern. First into the space after it and then we
241 copy it back. Be careful with the non-commutative functions. There the
242 worst one should decide.
243*/
244 p = pat + 1;
245 p2 = info;
246 for ( i = 0; i < numfun; i++ ) {
247 if ( i == nc ) {
248 for ( k = 0; k <= nc; k++ ) {
249 if ( AN.FunInfo[k].commute ) {
250 p1 = AN.FunInfo[k].location; j = p1[1];
251 NCOPY(p2,p1,j)
252 }
253 }
254 }
255 else if ( AN.FunInfo[i].commute == 0 ) {
256 p1 = AN.FunInfo[i].location; j = p1[1];
257 NCOPY(p2,p1,j)
258 }
259 }
260 p = pat + 1; p1 = info;
261 while ( p1 < p2 ) *p++ = *p1++;
262/*
263 And now we place the relevant information in the info part
264*/
265 p2 = info+1;
266 for ( i = 0; i < numfun; i++ ) {
267 if ( i == nc ) {
268 for ( k = 0; k <= nc; k++ ) {
269 if ( AN.FunInfo[k].commute ) {
270 finf = AN.FunInfo + k;
271 *p2++ = finf->numargs;
272 *p2++ = finf->numwildcards;
273 *p2++ = finf->numfunnies;
274 *p2++ = finf->symmet;
275 }
276 }
277 }
278 else if ( AN.FunInfo[i].commute == 0 ) {
279 finf = AN.FunInfo + i;
280 *p2++ = finf->numargs;
281 *p2++ = finf->numwildcards;
282 *p2++ = finf->numfunnies;
283 *p2++ = finf->symmet;
284 }
285 }
286 *info = p2-info;
287 lhs[1] = p2-lhs;
288 return(0);
289}
290
291/*
292 #] StudyPattern :
293 #[ MatchIsPossible :
294
295 We come here when there are functions and there is nontrivial
296 symmetry related wildcarding.
297*/
298
299int MatchIsPossible(WORD *pattern, WORD *term)
300{
301 GETIDENTITY
302 WORD *info = pattern + *pattern;
303 WORD *t, *tstop, *tt, *inf, *p;
304 int numfun = 0, inpat, i, j, numargs;
305 FUN_INFO *finf;
306/*
307 We need a list of functions and their number of arguments
308*/
309 GETSTOP(term,tstop);
310 t = term + 1;
311 while ( t < tstop ) {
312 if ( *t >= FUNCTION ) numfun++;
313 t += t[1];
314 }
315 if ( numfun == 0 ) goto NotPossible;
316 if ( *info == SETSET ) info += info[1];
317 inpat = (*info-1)/4;
318 if ( inpat > numfun ) goto NotPossible;
319/*
320 We need now some room for the information about the functions
321*/
322 if ( numfun > AN.numfuninfo ) {
323 if ( AN.FunInfo ) M_free(AN.FunInfo,"funinfo");
324 AN.numfuninfo = numfun + 10;
325 AN.FunInfo = (FUN_INFO *)Malloc1(AN.numfuninfo*sizeof(FUN_INFO),"funinfo");
326 }
327 t = term + 1; finf = AN.FunInfo;
328 while ( t < tstop ) {
329 if ( *t >= FUNCTION ) {
330 finf->location = t;
331 if ( functions[*t-FUNCTION].spec >= TENSORFUNCTION ) {
332 numargs = t[1]-FUNHEAD;
333 t += t[1];
334 }
335 else {
336 numargs = 0;
337 tt = t + t[1];
338 t += FUNHEAD;
339 while ( t < tt ) {
340 numargs++;
341 NEXTARG(t)
342 }
343 }
344 finf->numargs = numargs;
345 finf++;
346 }
347 else t += t[1];
348 }
349/*
350 Now we first find a partner for each function in the pattern
351 with a fixed number of arguments
352*/
353 for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
354 if ( inf[2] ) continue;
355 if ( *p >= (FUNCTION+WILDOFFSET) ) continue;
356 for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
357 if ( *p == *(finf->location) && *inf == finf->numargs ) {
358 finf->numargs = -finf->numargs-1;
359 break;
360 }
361 }
362 if ( j >= numfun ) goto NotPossible;
363 }
364 for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
365 if ( inf[2] ) continue;
366 if ( *p < (FUNCTION+WILDOFFSET) ) continue;
367 for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
368 if ( *inf == finf->numargs ) {
369 finf->numargs = -finf->numargs-1;
370 break;
371 }
372 }
373 if ( j >= numfun ) goto NotPossible;
374 }
375 for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
376 if ( inf[2] == 0 ) continue;
377 if ( *p >= (FUNCTION+WILDOFFSET) ) continue;
378 for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
379 if ( *p == *(finf->location) && (*inf-inf[2]) <= finf->numargs ) {
380 finf->numargs = -finf->numargs-1;
381 break;
382 }
383 }
384 if ( j >= numfun ) goto NotPossible;
385 }
386 for ( i = 0, inf = info+1, p = pattern+1; i < inpat; i++, inf += 4, p+=p[1] ) {
387 if ( inf[2] == 0 ) continue;
388 if ( *p < (FUNCTION+WILDOFFSET) ) continue;
389 for ( j = 0, finf = AN.FunInfo; j < numfun; j++, finf++ ) {
390 if ( (*inf-inf[2]) <= finf->numargs ) {
391 finf->numargs = -finf->numargs-1;
392 break;
393 }
394 }
395 if ( j >= numfun ) goto NotPossible;
396 }
397/*
398 Thus far we have determined that for each function in the pattern
399 there is a potential partner with enough arguments.
400 For now the rest is up to the real pattern matcher.
401
402 To undo the disabling of the number of arguments we need this code
403 for ( i = 0, finf = AN.FunInfo; i < numfun; i++, finf++ ) {
404 if ( finf->numargs < 0 ) finf->numargs = -finf->numargs-1;
405 }
406*/
407 return(1);
408NotPossible:
409/*
410 PrintTerm(pattern,"p");
411 PrintTerm(term,"t");
412*/
413 return(0);
414}
415
416/*
417 #] MatchIsPossible :
418*/